Geodesic
γ-graphs of graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 517-531 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: dominating sets, gamma graphs 
@article{DMGT_2011_31_3_a7,
     author = {Fricke, Gerd and Hedetniemi, Sandra and Hedetniemi, Stephen and Hutson, Kevin},
     title = {\ensuremath{\gamma}-graphs of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {517--531},
     year = {2011},
     volume = {31},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a7/}
}
TY  - JOUR
AU  - Fricke, Gerd
AU  - Hedetniemi, Sandra
AU  - Hedetniemi, Stephen
AU  - Hutson, Kevin
TI  - γ-graphs of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 517
EP  - 531
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a7/
LA  - en
ID  - DMGT_2011_31_3_a7
ER  - 
%0 Journal Article
%A Fricke, Gerd
%A Hedetniemi, Sandra
%A Hedetniemi, Stephen
%A Hutson, Kevin
%T γ-graphs of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 517-531
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a7/
%G en
%F DMGT_2011_31_3_a7
Fricke, Gerd; Hedetniemi, Sandra; Hedetniemi, Stephen; Hutson, Kevin. γ-graphs of graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 517-531. http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a7/

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

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

[3] E. Connelly, S.T. Hedetniemi and K.R. Hutson, A Note on γ-Graphs, submitted.

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

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).

[6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962.