OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT GRAPHS
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:
PDFReferences
- 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
Article Metrics
Metrics Loading ...
Refbacks
- There are currently no refbacks.