Open packing number for some classes of perfect graphs. (English) Zbl 1462.05154

Chandrasekar, K. Raja; Saravanakumar, S.

Ural Math. J. 6, No. 2, 38-43 (2020).

Summary: 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.

MSC:

05C17	Perfect graphs
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

open packing number; 2-packing number; perfect graphs; trestled graphs

References:

[1]	Aparna Lakshmanan S., Vijayakumar A., “The \(\langle t\rangle \)-property of some classes of graphs”, Discrete Math., 309:1 (2009), 259-263 · Zbl 1200.05191
[2]	Berge C., The Theory of Graphs and its Applications, Methuen, London, 1962, 257 pp. · Zbl 0097.38903
[3]	Berge C., Graphs and Hypergraphs, North-Holland, London, 1973, 528 pp. · Zbl 0254.05101
[4]	Chartrand G., Lesniak L., Graphs and Digraphs, \(4^{th}\), Chapman and Hall/CRC, London, 2005, 386 pp. · Zbl 1057.05001
[5]	Chudnovsky M., Robertson N., Seymour P., Thomas R., “The strong perfect graph theorem”, Ann. Math., 164:1 (2006), 51—229 · Zbl 1112.05042
[6]	Fellows M., Fricke G., Hedetniemi S., Jacobs D., “The private neighbor cube”, SIAM J. Discrete Math., 7:1 (1994), 41-47 · Zbl 0795.05078
[7]	Fisher D. C., Mckenna P. A., Boyer E. D., “Hamiltonicity, diameter, domination, packing and biclique partitions of Mycielski”s graphs”, Discrete Appl. Math., 84:1-3 (1998), 93-105 · Zbl 0906.05043
[8]	Henning M. A., Slater P. J., “Open packing in graphs”, J. Combin. Math. Combin. Comput., 29 (1999), 3-16 · Zbl 0922.05040
[9]	Hougardy S., “Classes of perfect graphs”, Discrete Math., 306:19-20 (2006), 2529-2571 · Zbl 1104.05029
[10]	Lovász L., “Normal hypergraphs and the perfect graph conjecture”, Discrete Math., 2:3 (1972), 253-267 · Zbl 0239.05111
[11]	Meir A., Moon J. W., “Relations between packing and covering numbers of a tree”, Pacific J. Math., 61:1 (1975), 225-233 · Zbl 0315.05102
[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, 468-475 · Zbl 1404.05170
[13]	Mycielski J., “Sur le coloriage des graphes”, Colloq. Math., 3 (1955), 161-162 · Zbl 0064.17805
[14]	Sahul Hamid I., Saravanakumar S., “Packing parameters in graphs”, Discuss. Math. Graph Theory, 35 (2015), 5-16 · Zbl 1307.05183
[15]	Seinsche D., “On a property of the class of \(n\)-colorable graphs”, J. Combin. Theory Ser. B, 16:2 (1974), 191-193 · Zbl 0269.05103