# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

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

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