# γ-graphs of graphs

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

top

## Abstract

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

## How to cite

top

Gerd 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. [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. [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. [3] E. Connelly, S.T. Hedetniemi and K.R. Hutson, A Note on γ-Graphs, submitted.
4. [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. [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. [6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962.

top

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.