A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ) = (V(γ), E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ) if there exists a vertex v ∈ D₁ and a vertex w ∈ D₂ such that v is adjacent to w and D₁ = D₂ - {w} ∪ {v}, or equivalently, D₂ = D₁ - {v} ∪ {w}. In this paper we initiate the study of γ-graphs of graphs.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1562,
author = {Gerd H. Fricke and Sandra M. Hedetniemi and Stephen T. Hedetniemi and Kevin R. Hutson},
title = {$\gamma$-graphs of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {31},
year = {2011},
pages = {517-531},
zbl = {1229.05219},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1562}
}
Gerd H. Fricke; Sandra M. Hedetniemi; Stephen T. Hedetniemi; Kevin R. Hutson. γ-graphs of graphs. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 517-531. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1562/
[000] [1] E.J. Cockayne, S.E. Goodman and S.T. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4 (1975) 41-44, doi: 10.1016/0020-0190(75)90011-3. | Zbl 0311.68024
[001] [2] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261, doi: 10.1002/net.3230070305. | Zbl 0384.05051
[002] [3] E. Connelly, S.T. Hedetniemi and K.R. Hutson, A Note on γ-Graphs, submitted.
[003] [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). | Zbl 0890.05002
[004] [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). | Zbl 0883.00011
[005] [6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962.