Trees and unicyclic graphs are \(\gamma\)-graphs. (English) Zbl 1200.05162

Sridharan, N.; Subramanian, K.

J. Comb. Math. Comb. Comput. 69, 231-236 (2009).

Summary: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is said to be a dominating set of \(G\), if each \(v\in V-D\) is adjacent to at least one vertex of \(D\). The minimum cardinality of a dominating set of \(G\) is called the domination number of \(G\) and is denoted by \(\gamma(G)\). A dominating set \(D\) with cardinality \(\gamma(G)\) is called a \(\gamma\)-set of \(G\). Given a graph \(G\), a new graph, denoted by \(\gamma\cdot G\) and called \(\gamma\)-graph of \(G\), is defined as follows: \(V(\gamma\cdot G)\) is the set of all \(\gamma\)-sets of \(G\) and two sets \(D\) and \(S\) of \(V(\gamma\cdot G)\) are adjacent in \(\gamma\cdot G\) if and only if \(|D\cap S|= \gamma(G)-1\). A graph \(G\) is said to be \(\gamma\)-connected if \(\gamma\cdot G\) is connected. A graph \(G\) is said to be a \(\gamma\)-graph if there exists a graph \(H\) such that \(\gamma\). \(H\) is isomorphic to \(G\). In this paper we show that trees and unicyclic graphs are \(\gamma\)-graphs. Also we obtain a family of graphs which are not \(\gamma\)-graphs.

MSC:

05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05	Trees

Keywords:

domination; \(\gamma\)-graph