Trees and Unicyclic Graphs are $\gamma$-graphs

Abstract

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 .G$ and called the $\gamma$-graph of $G$, is defined as follows: $V(\gamma .G)$ is the set of all $\gamma$-sets of $G$ and two sets $D$ and $S$ of $V(\gamma .G)$ are adjacent in $\gamma .G$ if and only if $|D\cap S|=\gamma (G)–1$. A graph $G$ is said to be $\gamma$-connected if $\gamma .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.