# γ-graphs of graphs

Gerd H. Fricke; Sandra M. Hedetniemi; Stephen T. Hedetniemi; Kevin R. Hutson

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 517-531
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGerd H. Fricke, et al. "γ-graphs of graphs." Discussiones Mathematicae Graph Theory 31.3 (2011): 517-531. <http://eudml.org/doc/270927>.

@article{GerdH2011,

abstract = {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.},

author = {Gerd H. Fricke, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Kevin R. Hutson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {dominating sets; gamma graphs},

language = {eng},

number = {3},

pages = {517-531},

title = {γ-graphs of graphs},

url = {http://eudml.org/doc/270927},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Gerd H. Fricke

AU - Sandra M. Hedetniemi

AU - Stephen T. Hedetniemi

AU - Kevin R. Hutson

TI - γ-graphs of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 517

EP - 531

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

LA - eng

KW - dominating sets; gamma graphs

UR - http://eudml.org/doc/270927

ER -

## References

top- [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. Zbl0311.68024
- [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. Zbl0384.05051
- [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). Zbl0890.05002
- [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
- [6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.