Some classes of non-induced star-perfect graphs

Articles in Press

Document Type : Original paper

Authors

School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Australia

Abstract

For a given graph G, let θf(G) denote the minimum number of stars (not necessarily induced) needed to cover the vertices of G, and let αf(G) denote the maximum number of vertices in a set S⊆V(G) such that no two distinct vertices u,v∈S belong to the same subgraph of G that is a star. Clearly, θf(G)≥αf(G). A graph G is said to be \emph{non-induced star-perfect} if θf(H)=αf(H) for every induced subgraph H of G. A graph G is a \emph{domination graph} if every induced subgraph H of G contains a pair of vertices x,y such that NH(x)⊆NH[y]. 

In this paper, we investigate domination graphs that are non-induced star-perfect and explore well-known subclasses within this category. Additionally, we present an integer linear programming formulation that characterizes a polytope associated with the star-covering set and star-independence set of a graph.

Keywords

Main Subjects

References

[1] J. Alex and L. Caccetta, Characterization of induced star-perfect graphs, Submitted.
[2] J. Alex and L. Caccetta, A note on Lov´asz characterization of perfect graphs, Submitted.
[3] G. Andreatta, C. De Francesco, L. De Giovanni, and P. Serafini, Star partitions on graphs, Discrete Optim. 33 (2019), 1–18.  http://dx.doi.org/10.1016/j.disopt.2019.01.002
[4] G. Andreatta, L. De Giovanni, and P. Serafini, Optimal shift partitioning of pharmacies, Comput. Oper. Res. 55 (2015), 88–98. http://doi.org/10.1016/j.cor.2014.09.009
[5] Y. Asahiro, Y. Doi, E. Miyano, and H. Shimizu, Optimal approximation algorithms for maximum distance-bounded subgraph problems, Combinatorial Optimization and Applications (Cham) (Z. Lu, D. Kim, W. Wu, W. Li, and D.Z. Du,
eds.), vol. 9486, Springer International Publishing, 2015, pp. 586–600.
[6] C. Berge, Balanced matrices, Math. Program. 2 (1972), 19–31. http://dx.doi.org/10.1007/BF01584535
[7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, vol. 290, The Macmillan Press, Macmillan London, 1976.
[8] A.E. Brouwer, P. Duchet, and A. Schrijver, Graphs whose neighborhoods have no special cycles, Discrete Math. 47 (1983), 177–182.  http://doi.org/10.1016/0012-365X(83)90088-2
[9] A.H. Busch, A characterization of triangle-free tolerance graphs, Discrete Appl. Math. 154 (2006), no. 3, 471–477. http://doi.org/10.1016/j.dam.2005.06.010
[10] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, Progress on perfect graphs, Math. Program. 97 (2003), no. 1-2, 405–422.  http://doi.org/10.1007/s10107-003-0449-8
[11] V. Chv´atal, On certain polytopes associated with graphs, J. Comb. Theory, B 18 (1975), no. 2, 138–154. http://doi.org/10.1016/0095-8956(75)90041-6
[12] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming., Studies in Integer Programming (P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, eds.), Annals of Discrete Mathematics, vol. 1, Elsevier,
1977, pp. 145–162.
[13] E. Dahihaus, P. Hammer, F. Maffray, and S. Olariu, On domination elimination orderings and domination graphs, Graph-Theoretic Concepts in Computer Science (Berlin, Heidelberg) (E.W. Mayr, G. Schmidt, and G. Tinhofer, eds.),
Springer Berlin Heidelberg, 1995, pp. 81–92.  https://doi.org/10.1007/3-540-59071-4 39
[14] G.A. Dirac, On rigid circuit graphs, Abh. Math. Semin. Univ. Hambg. 25 (1961),  71–76. http://doi.org/10.1007/BF02992776
[15] G. Domke, S.T. Hedetniemi, and R. Laskar, Fractional packings, coverings and irredundance in graphs, Congr. Numer. 66 (1988), 227–238.
[16] P. Erdös, E.T. Ordman, and Y. Zalcstein, Clique partitions of chordal graphs, Comb. Prob. Comput. 2 (1993), no. 4, 409–415.  http://doi.org/10.1017/S0963548300000808
[17] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983), no. 2, 173 – 189. http://dx.doi.org/10.1016/0012-365X(83)90154-1
[18] D.R. Fulkerson and L.R. Ford, Flows in Networks, Princeton University Press Princeton, 1962.
[19] D.R. Fulkerson, A.J. Hoffman, and R. Oppenheim, On balanced matrices, Math. Program. 1 (1974), 120–132. http://doi.org/10.1007/BFb0121244
[20] T. Gallai, Maximum-minimum sätze über graphen, Acta Math. Hungar. 9 (1958), no. 3-4, 395–434, https://doi.org/10.1007/BF02020271
[21] S. Ghosh, Star and path perfect graphs, Master’s thesis, Christ University, Bengaluru India, 2019.
[22] S. Ghosh, G. Ravindra, and V.M. Abraham, Some properties of star-perfect graphs, Commun. Comb. Optim. (2024),
http://doi.org/10.22049/cco.2023.28076.1484
[23] M.C. Golumbic, R.E. Jamison, and A.N. Trenk, Archimedean φ-tolerance graphs, J. Graph Theory 41 (2002), no. 3, 179–194.  http://doi.org/10.1002/jgt.10060
[24] P. Hall†, On representatives of subsets, Classic Papers in Combinatorics (Ira Gessel and Gian-Carlo Rota, eds.), Birkh¨auser Boston, Boston, MA, 1987, pp. 58–62.  https://doi.org/10.1007/978-0-8176-4842-8 4
[25] C.T. Hoáng and N. Khouzam, On brittle graphs, J. Graph Theory 12 (1988), no. 3, 391–404. http://doi.org/10.1002/jgt.3190120310
[26] A.J. Hoffman, A.W.J. Kolen, and M. Sakarovitch, Totally-balanced and greedy matrices, SIAM J. Discrete Math. 6 (1985), no. 4, 721–730.  http://doi.org/10.1137/0606070
[27] S. Hougardy, Classes of perfect graphs, Discrete Math. 306 (2006), no. 19, 2529–2571. http://doi.org/10.1016/j.disc.2006.05.021
[28] M. S. Jacobson, F. R. McMorris, and M. Mulder, An introduction to tolerance intersection graphs, Proceedings of the Sixth International Conference on Theory and Applications of Graphs, vol. 16, 1991, pp. 705–724.
[29] J. Lehel and Z. Tuza, Neighborhood perfect graphs, Discrete Math. 61 (1986),  no. 1, 93 – 101. http://dx.doi.org/10.1016/0012-365X(86)90031-2
[30] L. Lovász, Combinatorial Problems and Exercises, American Mathematical Society, New York, 2007.
[31] A. Meir and J. Moon, Relations between packing and covering numbers of a tree, Pac. J. Math. 61 (1975), no. 1, 225–233.  http://dx.doi.org/10.2140/pjm.1975.61.225
[32] G. Ravindra, Open problems, Second India-Taiwan conference on Discrete Mathematics (2011).
[33] G. Ravindra, F-perfect graphs, National Conference on Numerical methods and Network Analysis, July 17 to 18, Kallianpur (India), Milagres College, 2014.
[34] G. Ravindra, S. Ghosh, and V.M. Abraham, Odd sun-free triangulated graphs are s-perfect, 2023. https://arxiv.org/abs/2305.03540
[35] G. Ravindra, S. Ghosh, J.V. Kureethara, and V.M. Abraham, A characterization of star-perfect graphs, AKCE Int. J. Graphs Comb. 21 (2024), no. 2, 189–197.  http://doi.org/10.1080/09728600.2024.2329927
[36] B. Reed and N. Sbihi, Recognizing bull-free perfect graphs, Graphs Combin. 11 (1995), no. 2, 171–178. http://doi.org/10.1007/BF01929485
[37] I. Rusu and J. Spinrad, Domination graphs: examples and counterexamples, Discrete Appl. Math. 110 (2001), no. 2, 289–300.  http://doi.org/10.1016/S0166-218X(00)00274-2
[38] J. Sawada and J.P. Spinrad, From a simple elimination ordering to a strong elimination ordering in linear time, Inf. Process. Lett. 86 (2003), no. 6, 299–302. http://dx.doi.org/10.1016/S0020-0190(03)00228-X
[39] O. Stephan, Paw-free graphs, Inf. Process. Lett. 28 (1988), no. 1, 53–54. http://doi.org/10.1016/0020-0190(88)90143-3
[40] J. Topp and P. Zyliński, On domination perfect graphs, 2018.  https://arxiv.org/pdf/1802.03392
[41] A. Tucker, Perfect graphs and an application to optimizing municipal services, SIAM Review 15 (1973), no. 3, 585–590. http://doi.org/10.1137/1015072
[42] B. Zelinka, Domatically critical graphs, Czechoslov. Math. J. 30 (1980), no. 3,  486–489. http://dml.cz/dmlcz/101697
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 23 May 2025

Files

Share

How to cite

Statistics