OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT GRAPHS

K. Raja Chandrasekar     (Department of Mathematics, Amrita College of Engineering and Technology, Amritagiri, Erachakulam Post Nagercoil-629902, Tamil Nadu, India)
S. Saravanakumar     (Department of Mathematics, Kalasalingam Academy of Research and Education, Anand Nagar, Krishnankoil-626126, Tamil Nadu, India)

Abstract


Let \(G\) be a graph with the vertex set \(V(G)\).  A subset \(S\) of \(V(G)\) is an open packing set of \(G\) if every pair of vertices in \(S\) has no common neighbor in \(G.\)  The maximum cardinality of an open packing set of \(G\) is the open packing number of \(G\) and it is denoted by \(\rho^o(G)\).  In this paper, the exact values of the open packing numbers for some classes of perfect graphs, such as split graphs, \(\{P_4, C_4\}\)-free graphs, the complement of a bipartite graph, the trestled graph of a perfect graph are obtained.

Keywords


Open packing number, 2-packing number, Perfect graphs, Trestled graphs

Full Text:

PDF

References


Aparna Lakshmanan S., Vijayakumar A. The \(\langle t\rangle\) - property of some classes of graphs. Discrete Math., 2009. Vol. 309, No. 1. P. 259–263. DOI: 10.1016/j.disc.2007.12.057

Berge C. The Theory of Graphs and its Applications. London: Methuen, 1962. 257 p.

Berge C. Graphs and Hypergraphs. London: North-Holland, 1973. 528 p.

Chartrand G., Lesniak L. Graphs and Digraphs. 4 th ed. London: Chapman and Hall/CRC, 2005. 386 p.

Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem. Ann. Math., 2006. Vol. 164, No. 1. P. 51–229. DOI: 10.4007/annals.2006.164.51

Fellows M., Fricke G., Hedetniemi S., Jacobs D. The private neighbor cube. SIAM J. Discrete Math., 1994. Vol. 7, No. 1. P. 41–47. DOI: 10.1137/S0895480191199026

Fisher D.C., Mckenna P.A., Boyer E.D. Hamiltonicity, diameter, domination, packing and biclique partitions of Mycielski’s graphs. Discrete Appl. Math., 1998. Vol. 84, No. 1–3. P. 93–105. DOI: 10.1016/S0166-218X(97)00126-1

Henning M.A., Slater P.J. Open packing in graphs. J. Combin. Math. Combin. Comput., 1999. Vol. 29. P. 3–16.

Hougardy S. Classes of perfect graphs. Discrete Math., 2006. Vol. 306, No. 19-20. P. 2529–2571. DOI: 10.1016/j.disc.2006.05.021

Lovász L. Normal hypergraphs and the perfect graph conjecture. Discrete Math., 1972. Vol. 2, No. 3. P. 253–267. DOI: 10.1016/0012-365X(72)90006-4

Meir A., Moon J.W. Relations between packing and covering numbers of a tree. Pacific J. Math., 1975. Vol. 61, No. 1. P. 225–233. https://projecteuclid.org/euclid.pjm/1102868240

Mojdeh D.A., Samadi B., Khodkar A. and Golmohammadi H.R. On the packing numbers in graphs. Australas. J. Combin., 2018. Vol. 71, No. 3. P. 468–475. https://ajc.maths.uq.edu.au/pdf/71/ajc_v71_p468.pdf

Mycielski J. Sur le coloriage des graphes. Colloq. Math., 1955. Vol. 3. P. 161–162.

Sahul Hamid I., Saravanakumar S. Packing parameters in graphs. Discuss. Math. Graph Theory, 2015. Vol. 35. P. 5–16. DOI: 10.7151/dmgt.1775

Seinsche D. On a property of the class of n-colorable graphs. J. Combin. Theory Ser. B, 1974. Vol. 16, No. 2. P. 191–193. DOI: 10.1016/0095-8956(74)90063-X




DOI: http://dx.doi.org/10.15826/umj.2020.2.004

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.