PDF

Discussiones Mathematicae Graph Theory 31(3) (2011) 517-531
DOI: https://doi.org/10.7151/dmgt.1562

γ-Graphs of Graphs

Gerd H. Fricke Morehead State University Morehead, KY 40351, USA

Sandra M. Hedetniemi Stephen T. Hedetniemi Clemson University Clemson, SC 29634, USA

Kevin R. Hutson Furman University Greenville, SC 29613, USA

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.

Keywords: dominating sets, gamma graphs

2010 Mathematics Subject Classification: 05C69.

References

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

Received 4 June 2010
Revised 3 August 2010
Accepted 3 August 2010