Geodesic
Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 703-716.

Voir la notice de l'article provenant de la source Library of Science

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: domination, reconfiguration 
@article{DMGT_2018_38_3_a6,
     author = {Edwards, Michelle and MacGillivray, Gary and Nasserasr, Shahla},
     title = {Reconfiguring {Minimum} {Dominating} {Sets:} {The} {\ensuremath{\gamma}-Graph} of a {Tree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {703--716},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a6/}
}
TY  - JOUR
AU  - Edwards, Michelle
AU  - MacGillivray, Gary
AU  - Nasserasr, Shahla
TI  - Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 703
EP  - 716
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a6/
LA  - en
ID  - DMGT_2018_38_3_a6
ER  - 
%0 Journal Article
%A Edwards, Michelle
%A MacGillivray, Gary
%A Nasserasr, Shahla
%T Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 703-716
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a6/
%G en
%F DMGT_2018_38_3_a6
Edwards, Michelle; MacGillivray, Gary; Nasserasr, Shahla. Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 703-716. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a6/

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

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

[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/6097

[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.1562

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

[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_33

[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.

[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.005

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

[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.225

[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-T

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

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

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