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


  1. 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
  2. Berge C. The Theory of Graphs and its Applications. London: Methuen, 1962. 257 p.
  3. Berge C. Graphs and Hypergraphs. London: North-Holland, 1973. 528 p.
  4. Chartrand G., Lesniak L. Graphs and Digraphs. 4 th ed. London: Chapman and Hall/CRC, 2005. 386 p.
  5. 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
  6. 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
  7. 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
  8. Henning M.A., Slater P.J. Open packing in graphs. J. Combin. Math. Combin. Comput., 1999. Vol. 29. P. 3–16.
  9. 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
  10. 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
  11. 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
  12. 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
  13. Mycielski J. Sur le coloriage des graphes. Colloq. Math., 1955. Vol. 3. P. 161–162.
  14. Sahul Hamid I., Saravanakumar S. Packing parameters in graphs. Discuss. Math. Graph Theory, 2015. Vol. 35. P. 5–16. DOI: 10.7151/dmgt.1775
  15. 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.