Introducing 3-Path Domination in Graphs

Proof. We will use the known NP-complete domination problem,“For a given graph $G$ and a positive integer $k$, is $\gamma (G)\le k$?” [5]. Let $V(G)=\{v_1,v_2,\dots ,v_n\}$. Construct graph $H$ by letting $V(G_i)=\{v_1^i,v_2^i,\dots ,v_n^i\}$ for $1\le i\le 6$ and letting $v_h^i{v}_j^i\in E(G_i)$ if and only if $v_h{v}_j\in E(G)$. Let $H$ be the graph created by these six disjoint copies of $G$ and by adding the following edges. Let $v_h^1{v}_j^2$, $v_h^3{v}_j^4$, and $v_h^5{v}_j^6$ be in $E(H)$ if and only if either $h=j$ or $v_h{v}_j\in E(G)$. Add the edges $v_h^1{v}_h^3$ and $v_h^3{v}_h^5$ for $1\le h\le n$ to $H$. Thus the graph $H$ has $6n$ vertices and can be constructed from $G$ in polynomial time.

We claim that $\gamma (G)\le k$ if and only if ${\gamma }_{P_3}(H)\le k$.

Assume $D\subset V(G)$ is a dominating set of $G$ with $||D\le k$. Let $R$ be a set of 3-paths with $R=\{\{v_h^1,v_h^3,v_h^5\}|v_h\in D\}$. Thus R is a 3-path dominating set of H with $||R\le k$, so ${\gamma }_{P_3}(H)\le k$.

Now, assume $R$ is a 3-path dominating set of $G$ with $||R\le k$. Let $T=\bigcup _{Q_i\in R}V(Q_i)$. Since 3-paths are not necessarily disjoint and have 3 vertices each, $||T\le 3k$. Thus since $G_1\cup G_2\cong G_3\cup G_4\cong G_5\cup G_6$, we can assume that $||T_{1,2}=||T\cap (V(G_1)\cup V(G_2))\le k$. Let $T^{\ast }=\{v_h^2|v_h^1\in T_{1,2}\}\cup (T\cap V(G_2))$. Then $||T^{\ast }\le ||T_{1,2}\le k$ and $T^{\ast }$ dominates $V(G_2)$. Hence, $\gamma (G)\le k$. 

Proof. Let $D$ be a ${\gamma }_{P_3}$-set of $G$ and $V(D)$ be the set of vertices in $D$. Then $|V(D)|\le 3|D|=3{\gamma }_{P_3}(G)$ since some 3-paths may share vertices. Furthermore, $|V(D)|\ge \gamma (G)$ as $V(D)$ forms a dominating set of $G$. So we have $$3{\gamma }_{P_3}(G)\ge |V(D)|\ge \gamma (G),$$ and solving yields ${\gamma }_{P_3}(G)\ge \frac{\gamma (G)}{3}$. 

Proof. Let $D$ be a ${\gamma }_{P_3}$-set of a graph $G$ on $n$ vertices, and let $T$ be the set of edges in $G$ having one vertex in $V(D)$ and the other in $V(G)\setminus V(D)$. Since $\mathrm{\Delta }(G)\ge \mathrm{deg}(v)$ for all $v\in V(D)$ and each vertex in $V(D)$ has at least one neighbor in $V(D)$, $$|T|=t\le (\mathrm{\Delta }(G)-1)|V(D)|\le (\mathrm{\Delta }(G)-1)3{\gamma }_{P_3}(G).$$ In addition, $t\ge |V(G)\setminus V(D)|$ since there is at least one edge of $T$ incident to every vertex in $G$ that is not in $V(D)$. So, $$t\ge |V(G)\setminus V(D)|=n–|V(D)|\ge n-3{\gamma }_{P_3}(G).$$

So we have $n-3{\gamma }_{P_3}(G)\le t\le (\mathrm{\Delta }(G)-1)3{\gamma }_{P_3}(G)$, and solving yields ${\gamma }_{P_3}(G)\ge \frac{n}{3\mathrm{\Delta }(G)}$. 

Proof. Let $G$ be a graph with $|V(G)|\ge 3$ and $D$ be a ${\gamma }_{pr}$-set of $G$. Since there are $\frac{{\gamma }_{pr}(G)}{2}$ pairs of vertices in $D$ and $n\ge 3$, for each pair we can create a 3-path using the pair and a neighbor. This forms a 3-path dominating set with cardinality $\frac{{\gamma }_{pr}(G)}{2}$. 

Proof. Let $G$ be a graph and $D$ be a minimal 3-path dominating set on $G$. Suppose there are two 3-paths in $D$ that share an edge, $Q_1=\{v_1,v_2,v_3\}$ and $Q_2=\{v_2,v_3,v_4\}$. Consider the following two possibilities:

Referring to Figure 2, $Q_1$ and $Q_2$ each have at least one private neighbor. If $Q_1$ or $Q_2$ do not have any private neighbors, then $D$ is not minimal as $G$ would still be dominated if we remove one path without private neighbors. Let $p_1$ be a private neighbor of $Q_1$ and $p_2$ be a private neighbor of $Q_2$. Note, $p_1$ must be adjacent to $v_1$, and $p_2$ must be adjacent to $v_4$, otherwise they would be dominated by both $Q_1$ and $Q_2$. Without loss of generality, we set $Q_1^{\prime }=\{v_2,v_1,p_1\}$, making $Q_1^{\prime }$ and $Q_2$ edge-disjoint. Let $C=D-Q_1+Q_1^{\prime }$. Now $C$ is not guaranteed to be minimal. If $C$ is not minimal, it must be the case that $Q_1^{\prime }$ dominates what were the private neighbors of some other 3-path in $D$. Remove 3-paths from $C$ that do not have any private neighbors in $G$ with respect to $C$ to obtain a new minimal 3-path dominating set $D^{\prime }$. Repeat this process until $D^{\prime }$ is edge-disjoint and minimal. 

Proof. Let $G$ be a graph with $|V(G)|\ge 3$. By Theorem 5, there exists a minimal, edge-disjoint 3-path dominating set of $G$, call it $D$. Since no two 3-paths share an edge, and each 3-path contains two edges, $|D|\le \lfloor \frac{|E(G)|}{2}\rfloor$. 

Proof. Let $T$ be a tree with $diam(T)\ge 3$. Obtain a new graph $T^{\prime }$ by deleting all the leaves of $T$. Now $T^{\prime }$ has $n-L$ vertices. Using Corollary 1, we have ${\gamma }_{P_3}(T^{\prime })\le \lfloor \frac{n-L-1}{2}\rfloor$. Let $D^{\prime }$ be a 3-path dominating set of size $\lfloor \frac{n-L-1}{2}\rfloor$. Note that if $T^{\prime }$ has an even number of edges, this would be as if all the edges of $T^{\prime }$ were paired into disjoint 3-paths in $D^{\prime }$. Hence, if we added the $L$ vertices of $T$ back, all the support vertices of $T$ would be in one of the 3-paths of $D^{\prime }$ so $D^{\prime }$ would form a 3-path dominating set in $T$ as well. However, if $T^{\prime }$ has an odd number of edges, $|E(D^{\prime })|=n-L-2$, that is, there would be an edge of $T^{\prime }$, call it $e$, not included in the edge set of $D^{\prime }$. In $T$, it is possible that $e$ is incident to a support vertex. Hence we may need one more 3-path in $T$ than we needed in $T^{\prime }$. Therefore ${\gamma }_{P_3}(T)\le \lceil \frac{n-L-1}{2}\rceil$. 

Proof. Let $G$ be a graph on $n$ vertices and let $T_G$ be a spanning tree of $G$. Notice, since $V(T_G)=V(G)$ and $E(T_G)\subseteq E(G)$, we can construct $G$ from $T_G$ by adding the edges in $E(G)\setminus E(T_G)$. By Observation 6, ${\gamma }_{P_3}(G)\le {\gamma }_{P_3}(T_G)$. Since $T_G$ is a tree on $n$ vertices, ${\gamma }_{P_3}(T_G)\le \lceil \frac{n-L-1}{2}\rceil$ by Corollary 2. Since $L\ge 2$ for all trees with $n\ge 3$, ${\gamma }_{P_3}(G)\le \lceil \frac{n-3}{2}\rceil$. 

Proof. Let $T$ be a tree of order $n\ge 3$. We will proceed by induction on $n$. For $n=3$ we have $T=P_3$, and ${\gamma }_{P_3}(P_3)=1=\frac{3}{3}$.

Let $n>3$. Either there exists a longest path $P$ in $T$ such that one of the vertices on $P$ adjacent to its endvertices has degree greater than two, or the vertices adjacent the endvertices of every longest path have degree two. Note the endvertices of a longest path are leaves, and therefore the vertices adjacent to the endvertices on the path are support vertices. Refer to Figure 5 for an illustration of an example of a support vertex, $v$, of degree greater than two for Case 1, and of support vertices, labeled $m_i$, all of degree two for Case 2.

In Case 1, let $P$ be a longest path with a support vertex, $v$, adjacent to $k\ge 2$ leaves in $T$. Let $e$ be the edge of $P$ incident to $v$, but not to an endvertex of $P$. Then $T-e$ is a forest with components $T^{\prime }$ on $n-(k+1)$ vertices and $K_{1,k}$. If $n-(k+1)\le 2$, then $T$ is a star or a double star and we only need one $P_3$ to dominate $T$, which is less than $\frac{n}{3}$. If $n-(k+1)\ge 3$, the induction hypothesis gives ${\gamma }_{P_3}(T^{\prime })\le \frac{n-(k+1)}{3}$. Let $D^{\prime }$ be a 3-path dominating set of $T^{\prime }$ with $|D^{\prime }|\le \frac{n-(k+1)}{3}$. Note that we only require one 3-path, say $Q$, to dominate $K_{1,k}$. Thus $D=D^{\prime }\cup Q$ is a 3-path dominating set of $T$ with $|D|\le {\gamma }_{P_3}(T^{\prime })+1=\frac{n-(k+1)+3}{3}\le \frac{n}{3}$, since $k+1\ge 3$.

In Case 2, all the support vertices of the endvertices of the longest paths have degree two. Let $P$ be a longest path and let $v$ be a vertex on $P$ that is not a leaf and is adjacent to the support vertex of an endvertex of $P$, that is, a vertex that is distance $2$ away from an endvertex of $P$. Consider the neighbors of $v$ including neighbors not on $P$ and the support vertex of the endvertex of $P$. Label these $i$ neighbors $m_i$. Note that each $m_i$ is either degree two or degree one otherwise we contradict the assumption of Case 2. For any $m_i$ that has degree two, label its leaf neighbor ${\ell }_i$. Let $e$ be the edge of $P$ incident to $v$, but not to an endvertex of $P$. Then $T-e$ is a forest with components $H$ (containing $v$ and all the $m_i$ and ${\ell }_i$) and $T^{\prime }$.

If $|V(T^{\prime })|\le 2$, then $T$ is either $P_4$, $P_5$, or a spider with center vertex $v$ and legs of length one or two. Note that if $T$ is one of the two paths, we need only one $P_3$ to dominate it, which is less than $\frac{n}{3}$. Suppose $T$ is a spider with $k$ legs of length two, and $j$ legs of length one. If $k$ is even, then we create 3-paths between pairs of support vertices of the legs of length two to obtain a ${\gamma }_{P_3}$-set of size $\frac{k}{2}$. If $k$ is odd, we create pairs of support vertices using $k-1$ of the legs of length two, and add one 3-path from $v$ to the leaf of the unpaired leg of length two to obtain a ${\gamma }_{P_3}$-set of size $\frac{k+1}{2}$. (We use this method again when we look at banana trees in Theorem 4.5.) Note that in both cases, $n=2k+j+1$, and $\frac{k}{2}$ and $\frac{k+1}{2}$ are both less than $\frac{n}{3}$.

Suppose $|V(T^{\prime })|\ge 3$. Then $H$ is a spider. Let $k$ be the number of paths of the form $\{v,m_i,{\ell }_i\}$, i.e. legs of length two. If $k$ is even, then we dominate $H$ using $\frac{k}{2}$ many 3-paths and by the induction hypothesis ${\gamma }_{P_3}(T^{\prime })\le \frac{n-(2k+1)}{3}=\frac{n}{3}–\frac{2k+1}{3}$ ($H$ contains $v$, $2k$ vertices for each leg of length two, and possibly more vertices if $v$ has leaves as neighbors.) So $${\gamma }_{P_3}(T)\le {\gamma }_{P_3}(T^{\prime })+{\gamma }_{P_3}(H)\le \frac{n}{3}–\frac{2k+1}{3}+\frac{k}{2}=\frac{n}{3}–\frac{k+2}{6}\le \frac{n}{3}.$$ If $k$ is odd, then $k\ge 1$ and we need $\frac{k+1}{2}$ many 3-paths to dominate $H$, so similarly $${\gamma }_{P_3}(T)\le {\gamma }_{P_3}(T^{\prime })+{\gamma }_{P_3}(H)\le \frac{n}{3}–\frac{2k+1}{3}+\frac{k+1}{2}=\frac{n}{3}–\frac{k-1}{6}\le \frac{n}{3}.$$

By induction, we have shown that ${\gamma }_{P_3}(T)\le \frac{n}{3}$. 

Proof. Consider $P_n$ for $n\ge 3$. Suppose $n=5q+k$ for nonnegative integers $q$ and $k$, where $k<5$. We can partition $P_n$ into $q$ vertex-disjoint segments $S_i$, where $|V(S_i)|=5$, and one segment $S_{q+1}$ with $k$ vertices. (Refer to Figure 6.) We can dominate at most five vertices with a 3-path in $P_n$, specifically the three in the 3-path and potentially two others adjacent to the ends. Thus we need one 3-path for each $S_i$. Hence if $k=0$ we need $q$ 3-paths and if $k>0$ we need $q+1$ 3-paths. Hence ${\gamma }_{P_3}(P_n)\lceil \frac{n}{5}\rceil$.

The same argument holds for $C_n$, from which we can obtain $P_n$ by deleting one edge. 

Proof. Suppose $P$ is a Hamiltonian path of $G$. Then $P\cong P_n$ and since ${\gamma }_{P_3}(P_n)=\lceil \frac{n}{5}\rceil$ and $G$ is obtained from $P$ by adding edges, by Observation 6, we find that ${\gamma }_{P_3}(G)\le \lceil \frac{n}{5}\rceil$. 

Proof. Let $A$ be a caterpillar with stalk $S$ and $m=|V(S)|$. Then there exists a longest path, $P$, in $A$ of length $m+2$, such that $V(S)\subseteq V(P)$. Any vertex in $V(A\setminus P)$ must be a leaf that is adjacent to a vertex of $P$ that is not a leaf. Thus ${\gamma }_{P_3}(A)\ge {\gamma }_{P_3}(P)$ by Observation 12. By Theorem 11, ${\gamma }_{P_3}(P)\ge \lceil \frac{m+2}{5}\rceil$.

By Observation 8, a caterpillar in which every vertex of the stalk is a support vertex has a 3-path domination number at least as large as any caterpillar with in which at least one stalk vertex is not a support vertex. Thus we consider the case where every $v_i\in V(S)$ is a support vertex Then, each of the $v_i$ must be part of a 3-path by Observation 8. Furthermore, $V(S)$ is a dominating set of $A$. Thus a minimum 3-path dominating set would require that the 3-paths be as vertex disjoint as possible. At most two of the 3-paths would need to share vertices. Thus at most $\lceil \frac{m}{3}\rceil$ 3-paths are needed. 

Proof.

1. Note that $B_{n,1}$ is a star, $K_{1,n}$. Any 3-path in a star will contain the center vertex and thus dominate all vertices. Hence, ${\gamma }_{P_3}(B_{n,1})=1$.

2. For $k=2$, we pick our 3-paths with the following process. In $B_{n,2}$, the support vertices are the vertices adjacent to the root vertex. We make unique pairs of support vertices, and choose the unique 3-path between each pair to be in our dominating set. If $n$ is odd, then one support vertex is not in a pair and the last 3-path will include the leaf adjacent to the lone support vertex. See Figure [fig:banana1]. By Observation 1, every support vertex must be in a 3-path, so this is best possible.

   

3. For $k\ge 3$, by Observation 8, the center vertex of every copy of $K_{1,k-1}$ must be part of a 3-path. It is impossible to include any two centers in the same 3-path. So we must have a 3-path for each copy of $K_{1,k-1}$. We can insure that at least one of these 3-paths contains or is adjacent to the root vertex. Then one 3-path for each $K_{1,k-1}$ is best possible. Since we have $n$ copies, ${\gamma }_{P_3}(B_{n,k})=n$. See Figure 10.

Proof. Suppose we have $G=H_{k,n}$ where $k=2j$ for some integer $j$. Note that a Hamiltonian cycle exists in each Harary graph and we can assume the vertices around this cycle are labeled $v_1,\dots ,v_n$. To construct a 3-path dominating set of $G$, we create 3-paths as follows. Define a 3-path, $Q$, by choosing any vertex $v_m$ to be the middle vertex and then choose neighbors $v_{m-j}$ and $v_{m+j}$ to be the end vertices such that there is a path of length $\frac{k}{2}$ from $v_m$ to $v_{m-j}$ and $v_{m+j}$. Notice, $v_m$ dominates $k+1$ vertices, and each of $v_{m-j}$ and $v_{m+j}$ has an additional $\frac{k}{2}$ private neighbors with respect to $Q$ so long as $n$ is sufficiently large. So, $Q$ dominates $k+1+\frac{k}{2}+\frac{k}{2}=2k+1$ vertices. Note, $Q$ dominates the largest number of vertices possible by a 3-path in $G$. In addition, all the dominated vertices lie on a single path (Figure 11). Suppose $n=(2k+1)q+r$ where $0\le r\le 2k$. Then we can partition the labeled Hamiltonian cycle of $G$ into $q$ segments of $2k+1$ vertices and one segment with $r$ vertices. We choose a 3-path $Q$ for each of those segments, and thus we can dominate $G$ with $\lceil \frac{n}{2k+1}\rceil$ 3-paths and this is best possible.