In a graph, the distance between two vertices is the length of a shortest path connecting them. The distance-2 domination number \(\gamma_2(G)\) of a graph \(G\) is the minimum size of a vertex subset such that every vertex outside it is within distance two of some subset vertex. In a connected graph, a connected dominating set is a subset \(S\) whose induced subgraph is connected and in which every vertex not in \(S\) is adjacent to some vertex in \(S\); the connected domination number \(\gamma_c(G)\) is the size of a smallest such set. For \(k\ge 1\), let 𝒯k be the set of trees \(T\) satisfying \(\gamma_c(T)=2\gamma_2(T)=2k\). The collection 𝒯1 is the set of all double stars. In this paper, we provide a constructive characterization of 𝒯k for all \(k\ge 2\).
Domination and related subset problems constitute a rapidly expanding area of graph theory. Extensive studies on domination parameters can be found in the two books by Haynes et al. ([7, 8]). Determining the domination number of a graph is NP-complete, even for bipartite graphs ([8]).
Let \(G\) be a connected graph. A vertex subset \(S\) is a connected dominating set (CDS) if every vertex not in \(S\) is adjacent to at least one vertex in \(S\), and the subgraph \(\prec S \succ_G\) induced by \(S\) is connected. The connected domination number of \(G\), denoted by \(\gamma_c(G)\), is the minimum cardinality of a CDS. A connected dominating set (CDS) \(S\) is called a \(\gamma_c\)-set of \(G\) if \(|S|=\gamma_c(G)\). Desormeaux et al. ([6]) established several upper bounds for \(\gamma_c(G)\) and characterized the graphs achieving equality. Connected domination has important applications in routing problems and in the design of virtual backbone-based routing for wireless networks ([5, 9, 12]).
The concept of distance domination was introduced by Slater ([10]) and leads to NP-complete problems for general graphs ([3]). In this paper, we consider distance-2 domination. A set \(S\) is a distance-2 dominating set (D2DS) if every vertex not in \(S\) is within distance two from some vertex in \(S\). The distance-2 domination number of \(G\), denoted by \(\gamma_2(G)\), is the minimum cardinality of a D2DS. A distance-2 dominating set (D2DS) \(S\) is called a \(\gamma_2\)-set of \(G\) if \(|S|=\gamma_2(G)\). Sridharan et al. ([11]) established upper bounds for \(\gamma_2(G)\) and characterized the corresponding extremal graph classes. Subsequently, Bibi et al. ([1]) proposed algorithms for identifying minimal and minimum distance-2 dominating sets and explored related network applications ([2]).
In this paper, we investigate the particular domination parameters: distance-2 domination and connected domination. For \(k\ge 1\), let 𝒯\(_k\) be the set of trees \(T\) satisfying \(\gamma_c(T)=2\gamma_2(T)=2k\). The collection 𝒯\(_1\) is the set of all double stars. In this paper, we provide a constructive characterization of 𝒯\(_k\) for all \(k\ge 2\).
All graphs considered in this paper are finite and simple. For a graph \(G\), let \(V(G)\) and \(E(G)\) denote its vertex and edge sets, respectively. For \(v \in V(G)\), the open and closed neighborhoods of \(v\) are \[N_G(v)=\{u\in V(G):uv\in E(G)\}, \qquad N_G[v]=N_G(v)\cup\{v\}.\]
For \(A \subseteq V(G)\), define \[N_G(A)=\bigcup_{v\in A}N_G(v), \qquad N_G[A]=\bigcup_{v\in A}N_G[v].\]
The degree of \(v\) is \(\deg_G(v)=|N_G(v)|\). A vertex of degree one is a leaf, and a vertex adjacent to a leaf is a support vertex. Let \(L(G)\) and \(U(G)\) denote the sets of leaves and support vertices of \(G\), respectively. For sets \(A\) and \(B\), the set difference \(A-B\) consists of all elements of \(A\) not in \(B\). For \(A \subseteq V(G)\), the vertex-deletion \(G-A\) is obtained by removing all vertices in \(A\) and their incident edges; for \(B \subseteq E(G)\), the edge-deletion \(G-B\) is obtained by removing all edges in \(B\). Let \(P_n\) denote a path on \(n\) vertices, which has length \(n-1\). For two distinct vertices \(u,v\in V(G)\), a \(u\)–\(v\) path is a sequence \(u=v_1,\dots,v_k=v\) such that \(v_iv_{i+1}\in E(G)\) for \(1\le i<k\). The distance between \(u\) and \(v\), denoted by \(\mathrm{dist}_G(u,v)\), is the minimum length of a \(u\)–\(v\) path. The diameter of a nontrivial connected graph \(G\), denoted by \(diam(G)\), is the maximum distance between any two vertices of \(G\). The distance-2 closed neighborhood of \(v\) is \[N_G^2[v]=\{u\in V(G):\mathrm{dist}_G(u,v)\le2\},\] and for \(A\subseteq V(G)\), let \[N_G^2[A]=\bigcup_{v\in A}N_G^2[v].\]
A forest is an acyclic graph, and a tree is a connected forest. For \(A\subseteq V(G)\), the induced subgraph \(\prec A\succ_G\) has vertex set \(A\) and edge set \(\{uv\in E(G):u,v\in A\}\). The union \(G_1\cup G_2\) has vertex set \(V(G_1)\cup V(G_2)\) and edge set \(E(G_1)\cup E(G_2)\). The star \(S_n\) is the graph \(K_{1,n-1}\), and the double star \(S_{n,m}\) is obtained by joining the centers of two stars \(S_n\) and \(S_m\). For undefined terminology and notation, we refer the reader to [4].
We begin with the following observations.
Observation 2.1. If \(S\) is a D2DS of a graph \(G\), then \(N^2_G[S]=V(G)\).
Observation 2.2. If \(S\) is a \(\gamma_c\)-set of a tree \(T\), where \(|V(T)|\ge 3\), then \(S\cap L(T)=\emptyset\) and \(U(T)\subseteq S\).
Suppose, by contradiction, there exists a \(\gamma_c\)-set \(S\) of \(T\) such that \(S\cap L(T)\ne \emptyset\). Let \(x\in S\) and \(x\in L(T)\). Suppose \(y\) is the support vertex adjacent to \(x\) in \(T\). Since \(|V(T)|\ge 3\), it follows that \(y\notin L(T)\). Since \(\prec S\succ_T\) is connected and \(x\in S\), we obtain that \(y\in S\). Let \(S'=S-\{x\}\). Then \(S'\) is a CDS of \(T\) with cardinality \(|S'|=|S|-1=\gamma_c(T)-1\). This is a contradiction. So every \(\gamma_c\)-set of \(T\) contains no leaf, we obtain Observation 2.2.
The following lemmas are quite useful.
Lemma 2.3. Suppose \(T\) is a tree of order \(n\ge 3\), then there exists a \(\gamma_2\)-set \(S\)of \(T\) satisfying \(S\cap L(T)=\emptyset\).
Proof. Let \(S\) be a \(\gamma_2\)-set of \(T\). If \(S\cap L(T)=\emptyset\), then we are done. So we assume that \(S\cap L(T)=\{x_1,\dots,x_k\}\), where \(k\ge 1\). Let \(y_i\in N_T(x_i)\), where \(i=1,\dots,k\). By the minimality, it follows that \(y_i\notin S\) for all \(i\). Let \(S^*=(S-\{x_1,\dots,x_k\})\cup\{y_1,\dots,y_k\}\). Then \(S^*\) is a D2DS of \(T\) with cardinality \(|S^* |=|S|\). Thus we have that \(\gamma_2(T)\le |S^*|=|S|=\gamma_2(T)\), so \(|S^*|=\gamma_2(T)\). Hence \(S^*\) is a \(\gamma_2\)-set of \(T\) satisfying \(S^*\cap L(T)=\emptyset\). ◻
The following lemma identifies the unique \(\gamma_c\)-set in a tree \(T\).
Lemma 2.4. Suppose \(T\) is a tree of order \(n\ge 3\), then \(W(T)=V(T)-L(T)\) is the unique \(\gamma_c\)-set of \(T\) and \(\gamma_c(T)=|W(T)|\).
Proof. Let \(S\) be a \(\gamma_c\)-set of \(T\). By Observation 2.2, we obtain that \(L(T)\cap S=\emptyset\) and \(U(T)\subseteq S\). Suppose, by contradiction, \(S\ne W(T)\). Then there exists a vertex \(v\), where \(v\notin L(T)\), such that \(v\notin S\). By Observation 2.2, it follows that \(v\notin U(T)\). Thus the vertex-deletion subgraph \(T-\{v\}\) contains at least two components. Let \(C_1\) and \(C_2\) be two distinct components of \(T-\{v\}\). Since \(v\notin L(T)\) and \(v\notin U(T)\), we obtain that \(|V(C_i)|\ge 2\) and \(|V(C_i)\cap S|\ge|V(C_i)\cap U(T)|\ge 1\) for \(i=1\) and 2. Since \(T\) is a tree and \(v\notin S\), the induced subgraph \(\prec S\succ_T\) is disconnected. This is a contradiction, so \(S=W(T)\) is the unique \(\gamma_c\)-set of \(T\) and \(\gamma_c(T)=|W(T)|\). ◻
The inductive method employed in constructing 𝒯\(_k\) relies on Lemma 2.5
Lemma 2.5. Suppose \(T\) is a tree and \(P:x,y,z,w,t,p,\dots\) is a longest path of \(T\), where \(|V(P)|\ge 6\). Let \(e=zw\) and the edge-deletion \(T-\{e\}=T'\cup T''\), where \(w\in V(T'')\). Then \(\gamma_2(T'')=\gamma_2(T)-1\).
Proof. Let \(\gamma_2(T)=k\). Since \(|V(P)|\ge 6\), this implies that \(\gamma_2(T)=k\ge 2\). We can see that \(dist _T(v,x)\ge 3\) for every vertex \(v\in V(T'')\), so \(\gamma_2(T)\le \gamma_2(T)-1=k-1\). Suppose, by contradiction, there exists a \(\gamma_2\)-set \(S''\) of \(T''\) with cardinality \(|S''|\le k-2\). Then \(S=S''\cup\{z\}\) is a D2DS of \(T\) with cardinality \(|S|=|S''|+1\le k-1\). This is a contradiction, so \(\gamma_2(T'')=\gamma_2(T)-1\). ◻
The following lemma establishes a lower bound on the connected domination number, which is useful for characterizing the trees in 𝒯\(_k\).
Lemma 2.6. Let \(T\) be a tree and \(T\ne S_n\). Suppose \(\gamma_2(T)=k\), then \(\gamma_c(T)\ge2k.\)
Proof. We prove it by induction on \(k\). If \(\gamma_2(T)=1\), then \(T\) is a star or a double star. Note that \(T\ne S_n\), so \(T\) is a double star and \(\gamma_c(T)=2\). Thus it is true for \(k=1\). Assume that it’s true for \(k-1\), where \(k\ge 2\). Let \(T\) be a tree and \(\gamma_2(T)=k\), where \(k\ge 2\). Suppose \(P:x,y,z,w,t,p,\dots\) is a longest path of \(T\) and let \(e=zw\), where \(|V(P)|\ge 6\).. Let \(T-\{e\}=T'\cup T''\), where \(z\in V(T')\) and \(w\in V(T'')\). By Lemma 2.5, \(\gamma_2(T'')=k-1\). By the induction hypothesis, \(\gamma_c(T'')\ge 2(k-1)=2k-2\). Since \(\{y,z\}\cap L(T)=\emptyset\), by Lemma 2.4, \(\gamma_c(T)=|W(T)|=|W(T)\cap V(T')|+|W(T)\cap V(T'')|\ge |\{y,z\}|+\gamma_c(T'')\ge 2+ (2k-2)=2k\). Thus it is true for \(k\), we complete the proof. ◻
In this section, we characterize the set 𝒯\(_k\) for all \(k\ge 1\), where 𝒯\(_k\) is the collection of the trees \(T\) satisfying \(\gamma_c(T)=2\gamma_2(T)=2k\). First, we characterize the set 𝒯\(_1\).
Lemma 3.1. 𝒯\(_1\) is the collection of all double stars.
Proof. Let \(T\in 𝒯_1\). Since \(\gamma_c(T)=2\), by Lemma 2.4, \(|W(T)|=2\). So \(T\) is a double star. Hence 𝒯\(_1\) is the collection of all double stars. ◻
To provide a constructive characterization of 𝒯\(_k\) for \(k \ge 2\), we introduce the family \(ℱ_k\). A tree \(T\in ℱ_k\), where \(k\ge 2\), is defined to satisfy the following properties (I)\(\sim\)(VI) (see Figure 1).
(I) \(V(T)=A(T)\cup B(T)\cup L_0\cup( \bigcup_{i=1}^{k}L_i)\).
(II) Let \(W(T) = A(T) \cup B(T)\). The induced subgraph \(\prec W(T)\succ_T\) is a tree of order \(2k\).
(III) \(A(T)=\{z_1,z_2,\dots,z_k\}\) and \(\prec A(T)\succ_T\) is a tree.
(IV) \(B(T) = \{y_1, y_2, \dots, y_k\} = L(\prec W(T) \succ_T)\); that is, \(B(T)\) is the set of leaves of \(\prec W(T) \succ_T\).
(V) For each \(i=1,\dots,k\), \(L_i = L(T) \cap N_T(y_i) \ne \emptyset\).
(VI) \(L_0 = L(T) \cap N_T(A(T))\), which may be empty.
The following lemma establishes that every tree in \(ℱ_k\) belongs to 𝒯\(_k\).
Lemma 3.2. For \(k\ge 2\), \(ℱ_k\subseteq 𝒯_k\).
Proof. Suppose \(T\in ℱ_k\), then \(\gamma_c(T)=|W(T)|=2k\). Since \(A(T)\) is a D2DS of \(T\), it follows that \(\gamma_2(T)\le |A(T)|=k\). Suppose, by contradiction, there exists a \(\gamma_2\)-set \(S\) of \(T\) with cardinality \(|S|\le k-1\). There exists an index \(i\), where \(1\le i\le k\), such that \(S\cap L_i=\emptyset\) and \(S\cap \{y_i,z_i\}=\emptyset\). Then \(N^2_T[S]\ne V(T)\), so \(S\) is not a D2DS of \(T\). This is a contradiction, so \(\gamma_2(T)=k\). Then \(T\in 𝒯_k\). We complete the proof. ◻
Lemmas 3.3 and 3.4 prove the converse, showing that the reverse inclusion also holds.
Lemma 3.3. Suppose \(T\in 𝒯_2\), then \(T\inℱ_2\).
Proof. Let \(T\in 𝒯_2\). Then \(\gamma_2(T)=2\) and \(|W(T)|=\gamma_c(T)=4\). Suppose \(T'=\prec W(T)\succ_T\). Then \(T'\) is a tree of order 4, so \(T'=S_4\) or \(P_4\). Suppose, by contradiction, \(T'=S_4\). Then \(\gamma_2(T)=1\), this is a contradiction. Thus \(T'=P_4\), therefor \(T\inℱ_2\). ◻
Lemma 3.4. For \(k\ge 2\), 𝒯\(_k\subseteq ℱ_k\).
Proof. We prove it by induction on \(k\). By Lemma 3.3, it is true for \(k=2\). Assume that it is true for \(k-1\), where \(k\ge 3\). Let \(T\in 𝒯_k\). Then \(\gamma_2(T)=k\) and \(\gamma_c(T)=2k\). Since \(\gamma_2(T)=k\ge 3\), this follows that \(diam(T)\ge 5\). Let \(P:v_0,v_1,v_2,v_3,v_4,v_5,\dots\) be a longest path of \(T\) and let \(e=v_2v_3\). Suppose the edge-deletion \(T-\{e\}=T^*\cup T''\), where \(v_2\in V(T^*)\) and \(v_3\in V(T'')\). Note that \(T^*\) and \(T''\) are trees.
Claim 1. \(T''\in 𝒯_{k-1}\).
By Lemma 2.5 and Lemma 2.6, \(\gamma_2(T'')=k-1\) and \(\gamma_c(T'')\ge 2(k-1)=2k-2\). Then \(2k=\gamma_c(T)=|W(T)|=|W(T)\cap V(T^*)|+|W(T)\cap V(T'')|\ge |\{v_1,v_2\}|+|W(T'')|\ge 2+(2k-2)=2k\). The equalities all hold, thus \(\gamma_c(T'')=2(k-1)=2\gamma_2(T)\). Therefore, \(T''\in 𝒯_{k-1}\).
By Claim 1 and the induction hypothesis, \(T''\inℱ_{k-1}\). Then \(W(T'')=A(T'')\cup B(T'')\).
Claim 2. \(v_3\in A(T'')\).
Suppose, by contradiction, \(v_3\in L(T'')\). Then \(v_3\in W(T)\) and \(v_3\notin W(T'')\). So \(2k=\gamma_c(T)=|W(T)|=|W(T)\cap V(T^*)|+|W(T)\cap V(T'')|\ge 2+(|\{v_3\}|+|W(T'')|)=2+1+2k-2=2k+1\), this is a contradiction. Suppose, by contradiction, \(v_3=y_j\) for some \(y_j\in B(T'')\). Let \(z_m\in A(T'')\) be a neighbor of \(z_j\). Then \(N_T[z_j]\subseteq N^2_T[z_m]\) and \(L_j\subseteq N^2_T[v_2]\). Let \(S=(A(T'')-\{z_j\})\cup \{v_2\}\). Then \(S\) is a D2DS of \(T\) with cardinality \(|S|=|A(T'')|=k-1\). This is a contradiction again, so \(v_3\in A(T'')\).
Claim 3. \(T^*\) is a star or a double star.
Suppose, by contradiction, there exists another support vertex \(v'_1\), where \(v'_1\ne v_1\), adjacent to \(v_2\) in \(T^*\). Then \(2k=\gamma_c(T)=|W(T)|=|W(T)\cap V(T^*)|+|W(T)\cap V(T'')|\ge |\{v_2,v_1,v'_1\}|+|W(T'')|=3+2k-2=2k+1\), this is a contradiction. So \(W(T)\cap V(T^*)=\{v_1,v_2\}\), thus \(T^*\) is a star or a double star.
By Claim 2 and Claim 3, \(T\in ℱ_k\). Thus it is true for \(k\), we complete the proof. ◻
As an immediate consequence of Lemmas 3.2 and 3.4, we obtain Theorem 3.5, which establishes that 𝒯\(_k = ℱ_k\) for all \(k \ge 2\).
Theorem 3.5. For \(k\ge 2\), 𝒯\(_k= ℱ_k\).