Article in volume
Authors:
Title:
Elimination properties for minimal dominating sets of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 137-149
Received: 2019-10-01 , Revised: 2020-07-28 , Accepted: 2020-07-28 , Available online: 2020-09-09 , https://doi.org/10.7151/dmgt.2354
Abstract:
A dominating set of a graph is a vertex subset such that every vertex not in
the subset is adjacent to at least one in the subset. In this paper we study
whenever there exists a new dominating set contained (respectively, containing)
the subset obtained by removing a common vertex from the union of two minimal
dominating sets. A complete description of the graphs satisfying such
elimination properties is provided.
Keywords:
dominating sets, elimination properties, uniform clutters
References:
- V. Anusuya and R. Kala, A note on disjoint dominating sets in graphs, Int. J. Contemp. Math. Sciences 7 (2012) 2099–2110.
- P. Bose and F. Hurtado, Flips in planar graphs, Comput. Geom. 42 (2009) 60–80.
https://doi.org/10.1016/j.comgeo.2008.04.001 - D.L. Boutin, Determining sets, resolving sets, and the exchange property, Graphs Combin. 25 (2009) 789–806.
https://doi.org/10.1007/s00373-010-0880-6 - G. Chartrand and L. Lesniak, Graphs and Digraphs, Fourth Ed. (Chapman $\&$ Hall/CRC, Boca Raton, 2005).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
- M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458.
https://doi.org/10.1016/j.disc.2009.06.017 - M.M. Kanté, V. Limouzy, A. Mary and L. Nourine, On the enumeration of minimal dominating sets and related notions, SIAM J. Discrete Math. 28 (2014) 1916–1929.
https://doi.org/10.1137/120862612 - J. Martí-Farré, M. Mora and J.L. Ruiz, Uniform clutters and dominating sets of graphs, Discrete Appl. Math. 263 (2019) 220–233.
https://doi.org/10.1016/j.dam.2018.03.028 - J.G. Oxley, Matroid Theory, Second Ed. (Oxford Graduate Text in Mathematics, Oxford University Press, New York, 2011).
- D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).
- D.B. West, Introduction to Graph Theory, Second Ed. (Prentice Hall, Upper Saddle River, 2001).
Close