1. bookVolume 38 (2018): Issue 3 (August 2018)
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

Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 703 - 716
Received: 27 Jul 2016
Accepted: 02 Feb 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ- graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph.

Keywords

MSC 2010

[1] S. Alikhani, D. Fatehi and S. Klavžar, On the structure of dominating graphs (2015). arXiv:1512.07514Search in Google Scholar

[2] E. Connelly, K.R. Hutson and S.T. Hedetniemi, A note on γ-graphs, AKCE Int. J. Graphs Comb. 8 (2011) 23–31.Search in Google Scholar

[3] M. Edwards, Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs (PhD Thesis, Department of Mathematics and Statistics, University of Victoria, 2015). http://hdl.handle.net/1828/6097Search in Google Scholar

[4] G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi and K.R. Hutson, γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011) 517–531. doi:10.7151/dmgt.156210.7151/dmgt.1562Search in Google Scholar

[5] R. Haas and K. Seyffarth, The k-dominating graph, Graphs Combin. 30 (2014) 609–617. doi:10.1007/s00373-013-1302-310.1007/s00373-013-1302-3Search in Google Scholar

[6] A. Haddadan, T. Ito, A.E. Mouawad, N. Nishimura, H. Ono, A. Suzuki and Y. Tebbal, The complexity of dominating set reconfiguration, Lecture Notes in Comput. Sci. 9214 (2015) 398–409. doi:10.1007/978-3-319-21840-3_3310.1007/978-3-319-21840-3_33Search in Google Scholar

[7] J. van den Heuvel, The complexity of change, in: S.R. Blackburn, S. Gerke, M. Wildon (Eds.), Surveys in Combinatorics, London Mathematical Society Lecture Notes Series 409 (Cambridge University Press, 2013) 127–160.10.1017/CBO9781139506748.005Search in Google Scholar

[8] T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara and Y. Uno, On the complexity of reconfiguration problems, Theoret. Comput. Sci. 412 (2011) 1054–1065. doi:10.1016/j.tcs.2010.12.00510.1016/j.tcs.2010.12.005Search in Google Scholar

[9] S.A. Lakshmanan and A. Vijayakumar, The gamma graph of a graph, AKCE Int. J. Graphs Comb. 7 (2010) 53–59.Search in Google Scholar

[10] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225–233. doi:10.2140/pjm.1975.61.22510.2140/pjm.1975.61.225Search in Google Scholar

[11] M. Middendorf and F. Pfeiffer, Weakly transitive orientations, Hasse diagrams and string graphs, Discrete Math. 111 (1993) 393–400. doi:10.1016/0012-365X(93)90176-T10.1016/0012-365X(93)90176-TSearch in Google Scholar

[12] A.E. Mouawad, N. Nishimura and A. Suzuki, Reconfiguration of dominating sets (2014). arXiv:1401.5714Search in Google Scholar

[13] N. Sridharan and K. Subramanian, Trees and unicyclic graphs are γ-graphs, J. Combin. Math. Combin. Comput. 69 (2009) 231–236.Search in Google Scholar

[14] K. Subramanian and N. Sridharan, γ-graph of a graph, Bull. Kerala Math. Assoc. 5 (2008) 17–34.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo