On the structure of dominating graphs

Saeid Alikhani, Davood Fatehi, Sandi Klavžar

Published 2015-12-23Version 1

The $k$-dominating graph $D_k(G)$ of a graph $G$ is defined on the vertex set consisting of dominating sets of $G$ with cardinality at most $k$, two such sets being adjacent if they differ by either adding or deleting a single vertex. In this paper, after presenting several basic properties of $k$-dominating graphs, it is proved that if $G$ is a graph with no isolates, of order $n\ge 2$, and with $G\cong D_k(G)$, then $k=2$ and $G=K_{1,n-1}$ for some $n\ge 4$. The problem of which graphs are dominating graphs is also considered. In particular it is shown that paths and cycles of order at least $5$ are not dominating graph. Some results on the order of dominating graphs are also obtained.