1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Elimination Properties for Minimal Dominating Sets of Graphs

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Oct 2019
Accepted: 28 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] V. Anusuya and R. Kala, A note on disjoint dominating sets in graphs, Int. J. Contemp. Math. Sciences 7 (2012) 2099–2110.Search in Google Scholar

[2] P. Bose and F. Hurtado, Flips in planar graphs, Comput. Geom. 42 (2009) 60–80. doi:10.1016/j.comgeo.2008.04.00110.1016/j.comgeo.2008.04.001Search in Google Scholar

[3] D.L. Boutin, Determining sets, resolving sets, and the exchange property, Graphs Combin. 25 (2009) 789–806. doi:10.1007/s00373-010-0880-610.1007/s00373-010-0880-6Search in Google Scholar

[4] G. Chartrand and L. Lesniak, Graphs and Digraphs, Fourth Ed. (Chapman & Hall/CRC, Boca Raton, 2005).Search in Google Scholar

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).Search in Google Scholar

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).Search in Google Scholar

[7] M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458. doi:10.1016/j.disc.2009.06.01710.1016/j.disc.2009.06.017Search in Google Scholar

[8] 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. doi:10.1137/12086261210.1137/120862612Search in Google Scholar

[9] J. Martí-Farré, M. Mora and J.L. Ruiz, Uniform clutters and dominating sets of graphs, Discrete Appl. Math. 263 (2019) 220–233. doi:10.1016/j.dam.2018.03.02810.1016/j.dam.2018.03.028Search in Google Scholar

[10] J.G. Oxley, Matroid Theory, Second Ed. (Oxford Graduate Text in Mathematics, Oxford University Press, New York, 2011).Search in Google Scholar

[11] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).Search in Google Scholar

[12] D.B. West, Introduction to Graph Theory, Second Ed. (Prentice Hall, Upper Saddle River, 2001).Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo