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

[BIBTex] [PDF] [PS]

γ-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


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 D1 and D2, are adjacent in E( Γ) if there exists a vertex v ∈ D1 and a vertex w ∈ D2 such that v is adjacent to w and D1 = D2 −{w} ∪{v}, or equivalently, D2 = D1 −{v} ∪{w}. In this paper we initiate the study of Γ-graphs of graphs.

Keywords: dominating sets, gamma graphs

2010 Mathematics Subject Classification: 05C69.


[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