On the Structure of Dominating Graphs

Abstract

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. A graph is a dominating graph if it is isomorphic to $D_k(G)$ for some graph G and some positive integer k. Answering a question of Haas and Seyffarth for graphs without isolates, it is proved that if G is such a graph of order $n\ge 2$ and with $G\cong D_k(G)$, then $k=2$ and $G \cong K_{1,n-1}$ for some $n\ge 4$. It is also proved that for a given r there exist only a finite number of r-regular, connected dominating graphs of connected graphs. In particular, $C_6$ and $C_8$ are the only dominating graphs in the class of cycles. Some results on the order of dominating graphs are also obtained.

1 Introduction

Let S and $S'$ be dominating sets of order at most k of a graph G, where k is a given threshold. Then the dominating set reconfiguration (DSR) problem asks whether there exists a sequence of dominating sets of G starting with S and ending with $S'$, such that each dominating set in the sequence is of order at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. The problem is PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs, while on the positive side it can be solved in linear time for cographs, trees, and interval graphs [12].

The DSR problem naturally leads to the concept of the k-dominating graph introduced by Haas and Seyffarth [11] as follows. If G is a graph and k a positive integer, then the k-dominating graph $D_k(G)$ of G is the graph whose vertices correspond to the dominating sets of G that have cardinality at most k, two vertices of $D_k(G)$ being adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. (A similar concept is the one of $\gamma$-graphs in which only minimum dominating sets are considered as vertices of the derived graph [10].) Now, the DSR problem simply asks whether two given vertices of $D_k(G)$ belong to the same connected component of $D_k(G)$. Besides with the DSR problem, k-dominating graphs were further motivated by similar studies of graph colorings and by a general goal to further understand the relationship between dominating sets of a graph.

It follows from the above discussion that a fundamental problem about k-dominating graphs is to determine conditions which ensure that $D_k(G)$ is connected. This problem was the central theme of the seminal paper [11]. It is interesting to observe that the connectedness of $D_k(G)$ does not guarantee the connectedness of $D_{k+1}(G)$. For instance, $D_k(K_{1,n-1})$ ($n\ge 4$) is connected for any $1\le k\le n-2$, but $D_{n-1}(K_{1,n-1})$ is not connected. For the latter fact note that ${\varGamma }(K_{1,n-1}) = n-1$ and that in general $D_{{\varGamma }(G)}(G)$ is not connected. (Here ${\varGamma }(G)$ is the upper domination number of G, that is, the maximum cardinality of a minimal dominating set of G.) On the other hand, Haas and Seyffarth proved that if G has at least two disjoint edges and $k\ge \min \{n-1, {\varGamma }(G) + \gamma (G)\}$, then $D_k(G)$ is connected. Moreover, if G is bipartite or chordal, then $D_{{\varGamma }(G)+1}(G)$ is always connected. The connectivity of dominating graphs was further investigated in [18] where it was in particular demonstrated that there exists an infinite family of graphs such that $D_{\gamma (G)+1}(G)$ has exponential diameter and that $D_{n - \mu }(G)$ is connected for any graph G of order n and with a matching of size at least $\mu +1$.

In this paper we continue the study of k-dominating graphs and proceed as follows. In the next section, we introduce additional concepts needed, recall some basic properties of k-dominating graphs, and add additional results to this list. In Sect. 3, we attack the question from [11] where it was observed that $D_2(K_{1,n}) \cong K_{1,n}$ and asked whether there are other graphs G for which $D_k(G) \cong G$ holds. We prove that if G is of order $n\ge 2$ and with $\delta \ge 1$, and if $G\cong D_k(G)$, where $\gamma (G)\le k\le n$, then actually $G\cong K_{1,n-1}$ holds for some $n\ge 4$. Then, in Sect. 4, we prove that for any $r\ge 1$, there exist only a finite number of r-regular, connected dominating graphs of connected graphs. For $r=2$ we strengthen the result by showing that $C_6$ and $C_8$ are the only such graphs. We also show that among the paths, $P_1$ and $P_3$ are the only dominating graphs of connected graphs. In the final section we present some results on the order of k-dominating graphs, while along the way several problems for further study are stated.

2 Preliminaries

We use the notation $[n] = \{1,\ldots , n\}$. As usual, $\delta (G)$ and ${\varDelta }(G)$ denote the minimum and the maximum degree of a graph G, respectively. The order of a graph $G=(V,E)$ is denoted with |G|, that is, $|G| = |V|$, and the disjoint union of graphs G and H is denoted with $G\cup H$. The join $G+H$ of graphs G and H is obtained from the disjoint union of G and H by connecting each vertex of G with each vertex of H. We write $G\cong H$ to say that G and H are isomorphic graphs.

If $G = (V,E)$ is a graph, then $S\subseteq V$ is a dominating set of G if every vertex in $V - S$ is adjacent to at least one vertex in S. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G. A dominating set of the minimum cardinality is called a $\gamma$ -set. A vertex of G of degree $|G|-1$ is called a dominating vertex of G. For additional concepts from domination theory see [13].

We say that a graph is a dominating graph if it is isomorphic to $D_k(G)$ for some graph G and some positive integer k. For example, $C_6$ is a dominating graph because $D_2(K_3)\cong C_6$. In the next result we collect several basic properties about dominating graphs.

Proposition 1

If G is a graph, then the following hold.

• (i) If $\gamma (G)\le k\le |G|$, then $D_k(G)$ is bipartite.

• (ii) $|D_{|G|}(G)|$ is odd and $|D_{|G|-1}(G)|$ is even.

• (iii) If m is odd, $0< m < 2n$, then there exists a graph X of order n such that $|D_{n}(X)| = m$.

• (iv) If G is connected, then ${\varDelta }(D_{|G|}(G)) = |G|$.

Proof

• (i) Note that $D_n(K_n)$ is isomorphic to the graph obtained from the n-cube $Q_n$ by deleting one of its vertices. Since $D_k(G)$ is a subgraph of $D_k(K_n)$, and the latter graph is a subgraph of the bipartite graph $D_n(K_n)$, it follows that $D_k(G)$ is bipartite.

• (ii) That the order of $D_{|G|}(G)$ is odd follows immediately from a result of Brouwer, Csorba, and Schrijver [7, Theorem 1.1] asserting that the number of dominating sets of a finite graph is odd. As the only dominating set of order |G| of G is its vertex set, $D_{|G|-1}(G)$ is then of even order.

• (iii) This assertion follows from [7, Proposition 1.2] which asserts that if m is odd, where $0< m < 2n$, then there exists a graph of order n that contains precisely m dominating subsets (see also [1]).

• (iv) As $D_{|G|}(G)$ is a subgraph of $Q_{|G|}$ we infer that ${\varDelta }(D_{|G|}(G)) \le |G|$. On the other hand, since G is connected, any $(|G|-1)$-subset of vertices is a dominating set and adjacent to the whole vertex set in $D_{|G|}(G)$. So V(G) is of degree |G| in $D_{|G|}(G)$. $\square$

$D_{|G|}(G)$ is not regular unless G is an edge-less graph in which case $D_{|G|}(G)\cong K_1$. Note also that from Proposition 1(i) and (ii) it follows that $D_{|G|}(G)$ is not Hamiltonian. On the other hand, the question of which k-dominating graphs $D_k(G)$ with $k < |G|$ are Hamiltonian remains an open problem.

3 Graphs Isomorphic to Their Dominating Graphs

Haas and Seyffarth [11] observed that $D_2(K_{1,n}) \cong K_{1,n}$ and posed the question whether there are other graphs G for which $D_k(G) \cong G$. In the next result we prove that the answer is negative as soon as G has no isolated vertices.

Theorem 1

Let G be a graph of order $n\ge 2$ and with $\delta \ge 1$. If $G\cong D_k(G)$, then $k=2$ and $G\cong K_{1,n-1}$ for some $n\ge 4$.

Proof

Assume first that $k=\gamma (G)$. Then $V(D_k(G))$ consists of $\gamma$-sets of G and hence $D_k(G)$ is an edge-less graph. If $G\cong D_k(G)$, this is only possible when $G=K_1$. As we have assumed that G is of order at least 2, we may suppose in the rest of the proof that $k\ge \gamma (G)+1$.

Let $V(G) = \{v_1,\ldots , v_n\}$ and set $\gamma = \gamma (G)$. Let X be a $\gamma$-set of G, where we may without loss of generality assume that $X = \{v_1,\ldots , v_\gamma \}$. Assume that $G\cong D_k(G)$ and recall that $k\ge \gamma +1$. Then $X_i = X\cup \{v_i\}, \gamma +1\le i\le n$, are dominating sets of G and hence vertices of $D_k(G)$. As they are all of cardinality $\gamma +1$, the vertices $X,X_{\gamma +1}, \ldots , X_n$ induce a $K_{1,n-\gamma }$ in $D_k(G)$ (hence G also contains an induced $K_{1,n-\gamma }$). Let ${{{\mathcal {Y}}}} = \{Y_1,\ldots , Y_{\gamma -1}\}$ be the remaining vertices of $D_k(G)$. Observe that the vertex $Y_i, i\in [\gamma -1]$, is not adjacent to X, for otherwise $\{X\} \cup \{Y_j:j\ne i\}$ would be a dominating set of $D_k(G)$, but then (since $G\cong D_k(G)$) we would have a dominating set of G smaller than $\gamma$. Moreover, a vertex $X_i, \gamma +1\le i\le n$, can be adjacent to at most one vertex from ${{{\mathcal {Y}}}}$. Indeed, suppose that, without loss of generality, $X_{\gamma +1}$ is adjacent to $Y_1$ and $Y_2$. Then $\{X, X_{\gamma +1}, Y_{3}, \ldots , Y_{\gamma -1}\}$ is a dominating set of $D_k(G)$ yielding the same contradiction as above.

If for some $i\ne j, Y_i$ would be adjacent to $Y_j$, then $\{X,Y_1,\ldots Y_{\gamma -1}\}\setminus \{Y_j\}$ would be a dominating set of $D_k(G)$ of size $\gamma - 1$. Hence, since by the theorem’s assumption G has no isolated vertices, each $Y_i$ has a neighbor in ${{{\mathcal {X}}}} = \{X_{\gamma +1}, \ldots , X_n\}$. Since furthermore no $X_j$ is adjacent to two vertices from ${{{\mathcal {Y}}}}$, we find out that there exists a matching from ${{{\mathcal {Y}}}}$ to ${{{\mathcal {X}}}}$. Let $\{X_{i_1},\ldots , X_{{i_{\gamma -1}}}\}$ be the endpoints of the matching edges which lie in ${{{\mathcal {X}}}}$. Then $\{X,X_{i_1},\ldots , X_{{i_{\gamma -1}}}\}$ is a dominating set of G of cardinality $\gamma$ and we have the following two $\gamma$-sets of $D_k(G)$:

• $\{X,Y_{1},\ldots , Y_{\gamma -1}\}$   and

• $\{X,X_{i_1},\ldots , X_{{i_{\gamma -1}}}\}$.

Suppose that $\gamma \ge 2$. Adding to any of the above two $\gamma$-sets an additional vertex, we get a dominating set of cardinality $\gamma +1$. Since $\gamma \ge 2$, in this way we can construct $2(n-\gamma )-1$ different dominating sets of G of this cardinality. Consequently, $D_k(G)$ contains at least $2 + 2(n-\gamma )-1$ vertices. Since for any graph without isolated vertices $\gamma \le n/2$ holds, it follows that $D_k(G)$ contains at least $n+1$ vertices, a contradiction.

The only case left to consider is $\gamma = 1$. Assume without loss of generality that $v_1$ is a dominating vertex. Suppose that G contains another dominating vertex, say $v_2$, that is, $\mathrm{deg}(v_1) = \mathrm{deg}(v_2)=n-1$. Then $\{v_1\}, \{v_2\}, \{v_1, v_2\}, \{v_1,v_i\}$ ($i\ge 3$), and $\{v_2,v_i\}$ ($i\ge 3$), are dominating sets of G, hence $|D_2(G)|\ge 2n-1 > n$. Therefore $v_1$ is the unique dominating vertex of G. Now, since $D_2(G)$ is of order n, its dominating sets of order at most 2 are $\{v_1\}$ and $\{v_1,v_i\}$ ($i\ge 2$). But then $D_2(G)\cong K_{1,n-1}$ where $n\ge 4$. $\square$

Let G be an arbitrary graph with $\gamma (G)\ge 3$ and consider the join $G+K_1$, where $V(K_1) = \{x\}$. Clearly, $\gamma (G+K_1) = 1$. Moreover, if D is a dominating set of $G+K_1$ and $|D|=2$, then (since $\gamma (G)\ge 3$) we must have $x\in D$. It follows that $D_2(G+K_1) \cong K_{1,|G|}$. This example shows that the stars $K_{1,n}$ can be represented as dominating graphs in many different ways.

4 Realizability of Graphs as Dominating Graphs

Another problem from [11] is which graphs are dominating graphs. The main result of this section asserts that not many regular graphs are such. To state the result, a short preparation is needed.

For any $r\ge 1$ let $c_r$ be a given, fixed constant such that $\gamma (G) \le c_r|G|$ holds for any connected graph G with $\delta (G)=r$. As already observed by Ore [15], if $\delta (G)\ge 1$ then $\gamma (G)\le n/2$, so that we can set $c_1 = 1/2$. The constant $c_2 =2/5$ was independently obtained in [5, 14] (actually, there are seven small graphs: $C_4$, and six graphs on seven vertices, for which the 2/5 bound does not hold); the result $c_3 = 3/8$ is due to Reed [16]; $c_4 = 4/11$ is from [17]. For $k\ge 5$ the best known constants $c_k$ were recently developed in [9]. To obtain these constants a modification of a method from [8] was applied, which was in turn developed for the investigation of the domination game [6].

Now let $r\ge 1$. Then setting

$$\begin{aligned} {{{\mathcal {D}}}}_r = \{H:\ H\ \mathrm{is\ an}\ r\text{- }\mathrm{regular,\, connected \, dominating \ graph\ of\ a\ connected\ graph}\}, \end{aligned}$$

our result reads as follows.

Theorem 2

Let $r\ge 1$. If G is a connected graph such that for some $k, D_k(G)\in {{{\mathcal {D}}}}_r$, then $|G|\le 2r$. Consequently, $|{{{\mathcal {D}}}}_r| < \infty$.

Proof

Let G be a connected graph and suppose that $D_k(G)\cong H$, where H is an r-regular, connected graph and k is a positive integer. Clearly, $k\ge \gamma (G)+1$, for if $k=\gamma (G)$, then $D_k(G)$ is edgeless. Let X be a $\gamma$-set of G. Then for any vertex $y\notin X$, the set $X_y = X\cup \{y\}$ is a dominating set of order $\gamma (G)+1$. Hence $X_y$ is a neighbor of X in $D_k(G)$. Because there are $|G|-\gamma (G)$ such vertices y, we infer that $\deg _{D_k(G)}(X) \ge |G|-\gamma (G)$. Moreover, since X is a $\gamma$-set, no subset of X is a dominating set and consequently $\deg _{D_k(G)}(X) = |G|-\gamma (G)$. As $D_k(G)\cong H$ and H is r-regular, it follows that $r=|G|-\gamma (G)$. Since $\gamma (G) \le c_{\delta (G)}|G|$ we have $|G|-r = \gamma (G) \le c_{\delta (G)}|G|$. By the above mentioned Ore’s result, $c_{\delta (G)} \le 1/2$ holds, hence we find out that $|G|-r \le |G|/2$ and thus $|G|\le 2r$.

By the above it follows that for a given r, a graph $H\in {{{\mathcal {D}}}}_r$ can be realized as a dominating graph only with a graph G of order at most 2r (and for some fixed $k\le 2r$). As there are only a finite number of such graphs, $|{{{\mathcal {D}}}}_r| < \infty$. $\square$

We note that Theorem 2 can be extended to disconnected graphs. Suppose first that each component of a given graph G has at least two vertices. Then by the same argument as in the proof of Theorem 2 (applied to each of the components of G) we infer that $|G|\le 2r$. Suppose next that G contains isolated vertices and at least one component of order at least 2. Let $G'$ be the graph obtained by removing all the isolated vertices from G. Then $D_k(G') = D_{k+|G'|}(G)$ and hence no new regular dominating graphs can be obtained in this way. Finally, if G has no edges we only get $K_1$ as a dominating graph.

Theorem 2 strengthens in the case $r=2$ as follows.

Corollary 1

${{{\mathcal {D}}}}_2 = \{C_6, C_8\}$.

Proof

By Theorem 2, $|G|\le 4$ holds if G is a connected graph with $D_k(G)$ isomorphic to a 2-regular connected graph, that is, to a cycle. It is straightforward to verify by considering all the small cases that among connected graphs G of order at most 4 and among appropriate values k, the only favourable cases are $D_2(K_3) \cong C_6$ and $D_3(P_4) \cong C_8$. The fact that $D_3(P_4) \cong C_8$ can be verified using Fig. 1. $\square$

Fig. 1

$P_4$ and $D_3(P_4)$

A result parallel to Corollary 1 for paths reads as follows.

Proposition 2

Among the paths, $P_1$ and $P_3$ are the only dominating graphs of connected graphs.

Proof

By inspection on connected graphs of order at most 4 the only dominating graphs that are paths are $P_1 \cong D_1(K_1)$ and $P_3 \cong D_2(P_2)$.

Suppose now that $D_k(G)\cong P_m$ holds for some connected graph G with $|G|>4$ and for some k and m. Let X be a $\gamma$-set of G. Then either $\deg _{D_k(G)}(X)=1$ or $\deg _{D_k(G)}(X)=2$. Since clearly $k > \gamma (G)$, it follows that either $|G|-\gamma (G) = 1$ or $|G|-\gamma (G) = 2$. But since $\gamma (G) \le \frac{|G|}{2}$ and $|G|>4$, this is not possible. $\square$

In Corollary 1 and in Proposition 2 we have considered the dominating graphs that are derived from connected graphs. The following examples indicate that it would be interesting to extend the investigation to disconnected graphs: $D_3(K_2\cup K_2) \cong C_8$ and $D_3(K_2\cup K_1) \cong D_4(K_2\cup K_1\cup K_1) \cong P_3$. Similarly, in Theorem 2 we have assumed that the graph G considered has no isolated vertices, hence an extension to graphs that contain isolates could also be interesting.

5 On the Order of Dominating Graphs

The domination polynomial D(G, x) of G is defined as

$$\begin{aligned} D(G,x)=\sum _{i\ge 0} d(G,i) x^{i}, \end{aligned}$$

where d(G, i) is the number of dominating sets of G of cardinality i. This graph polynomial was introduced in the paper [3] that appeared in 2014, but numerous other papers on the polynomial appeared earlier. For some very recent developments on the polynomial see [4]. From our perspective, a key piece of information encoded in the domination polynomial is that

$$\begin{aligned} |D_{|G|}(G)| = D(G,1). \end{aligned}$$

For instance, using a result from [2] asserting that $D(C_1, x) = x, D(C_2, x) = x^2 + 2x, D(C_3, x) = x^3 + 3x^2 + 3x$, and

$$\begin{aligned} D(C_n, x) = x\left( D(C_{n-1}, x) + D(C_{n-2}, x) + D(C_{n-3}, x)\right) , \end{aligned}$$

for $n\ge 4$, we get the following result.

Proposition 3

$|D_1(C_1)|=1, |D_2(C_2)|=3, |D_3(C_3)|=7$, and

$$\begin{aligned} |D_n(C_n)|=|D_{n-1}(C_{n-1})|+|D_{n-2}(C_{n-2})|+|D_{n-3}(C_{n-3})|,\ n\ge 4. \end{aligned}$$

We conclude the paper by determining the order of the dominating graph of the join and the corona of two graphs in terms of the invariants of their factors. The join has already been defined, while the corona $G\circ H$ of graphs G and H is the graph obtained from the disjoint union of G and |G| copies of H by joining the ith vertex of G ($1\le i\le |G|$) to every vertex in the i-th copy of H.

Proposition 4

If G and H are graphs, then

• (i) $|D_{|G+H|}(G+H)|=(2^{|G|}-1)(2^{|H|}-1)+|D_{|G|}(G)|+|D_{|H|}(H)|$,

• (ii) $|D_{|G\circ H|}(G\circ H)|=(2^{|H|} +|D_{|H|}(H)|)^{|G|}$.

Proof

• (i) Note first that if $\emptyset \ne D_G \subseteq V(G)$ and $\emptyset \ne D_H \subseteq V(H)$, then $D_G\cup D_H$ is a dominating set of $G+H$. This gives $(2^{|G|}-1)(2^{|H|}-1)$ dominating sets of $G+H$. Assume now that D is a dominating set of $G+H$ with $D\cap V(G)=\emptyset$. Then $D\cap V(H)$ must be a dominating set of H, whence there are $|D_{|H|}(H)|$ such dominating sets of $G+H$. Analogously, if $D\cap V(H)=\emptyset$ we get $|D_{|G|}(G)|$ dominating sets of $G+H$.

• (ii) Let D be a dominating set of $G\circ H$ and assume that a vertex $x\in V(G)$ does not belong to D. If $H_x$ is the copy of H corresponding to x, then $D\cap V(H_x)$ is a dominating set of $H_x$. Therefore, if a vertex $x\in V(G)$ is not in D, it is dominated by a vertex from $H_x$. It follows that D is a dominating set of $G\circ H$ if and only if D is a dominating set of the graph $(G\circ H) - E(G)$. The latter graph is isomorphic to the disjoint union of |G| copies of the graph $K_1 + H$. By (i), $D_{|H|+1}(K_1+H) = 2^{|H|} +|D_{|H|}(H)|$ and consequently $|D_{|G\circ H|}(G\circ H)|=(2^{|H|} +|D_{|H|}(H)|)^{|G|}$. $\square$