γ-graphs of graphs

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