On Tight Bounds for the k-Forcing Number of a Graph

Abstract

The k-forcing number of a graph G, denoted by $F_k(G)$, was introduced by Amos et al. It is a generalization of the zero forcing number of a graph G, denoted by Z(G). Amos et al. proved that for a connected graph G of order n with maximum degree $\varDelta \ge 2$, $Z(G)=F_1(G)\le \frac{(\varDelta -2)n+2}{\varDelta -1}$, and this inequality is sharp. Moreover, they posed a conjecture that $Z(G)=F_1(G)=\frac{(\varDelta -2)n+2}{\varDelta -1}$ if and only if $G=C_n$, $G=K_{\varDelta +1}$ or $G=K_{\varDelta ,\varDelta }$. In this paper, we prove that this conjecture is true. Moreover, we point out a mistake in their paper and get a stronger result which shows that $F_{n-1}(G)=1$ if and only if G is connected and $F_k(G)=n-k$ if and only if $G=K_n$ for $k\le n-2$.

1 Introduction

We follow the notation and terminology of [4, 5] for those not defined here, and the graphs throughout this paper are simple, undirected and finite. For a graph $G=(V(G),E(G))$ and a vertex $v\in V(G)$, the neighborhood N(v) of v is defined as the set of vertices adjacent to v. The degree $d_G(v)$ of v is the number of edges incident with v in G. The minimum and maximum degrees of a graph G are denoted by $\delta (G)$ and $\varDelta (G)$, respectively. Throughout this paper, we will denote the minimum and maximum degrees of a graph G simply by $\delta$ and $\varDelta$, respectively. If $U\subseteq V(G)$ is any set of vertices, then the subgraph induced by U, denoted by G[U], is the graph on U whose edges are precisely the edges of G with both end vertices in U. For two disjoint vertex subsets of G, A and B, denote the set of the edges between A and B by E(A, B), and set $e(A,B)=|E(A,B)|$.

The notion of the k-forcing number was introduced and defined in [2]. Let $k \le \varDelta$ be a positive integer. Let G be a graph and S be a subset of V(G). The vertices in S are initially colored while the remaining vertices of G are initially uncolored. We call S a k-forcing set of a graph G if all vertices in G will eventually become colored such that the graph is subjected to the following color change rule: if a colored vertex is adjacent to at most k uncolored neighbors, then the uncolored neighbors change to be colored. Note that a colored vertex with at most k uncolored neighbors will cause each uncolored neighbor to be colored. The k-forcing number of G, denoted by $F_k(G)$, is the cardinality of a smallest k-forcing set. We will call the discrete dynamical process of applying this color change rule to S and G the k-forcing process. If a vertex v causes a vertex w to change color during the k-forcing process, we say that vk-forcesw.

This concept generalizes the recently introduced but heavily studied notion of the zero forcing (also called graph infection) number of a graph, which is denoted by $Z=Z(G)$. Indeed, $F_1(G) = Z(G)$. The zero forcing number was introduced independently in [1, 3]. In [1], it is introduced to bound from below the minimum rank of a graph, or equivalently, to bound from above the maximum nullity of a graph. Namely, if G is a graph whose vertices are labeled from 1 to n, then let M(G) denote the maximum nullity over all symmetric real-valued matrices where, for $i \ne j$, the ijth entry is nonzero if and only if $\{i, j\}$ is an edge in G. Then, the zero forcing number is an upper bound on M(G), that is, $F_1(G)=Z(G)\ge M(G)$. In [3], it is indirectly introduced in relation to a study of control of quantum systems.

Amos et al. [2] got the following result on the k-forcing number of complete graphs.

Proposition 1

[2] Let G be a complete graph on n vertices, and let k be a positive integer. Then, $F_k(G)=\max \{n-k,1\}$.

Below Proposition 1, they considered the complete bipartite graph $G=K_{3,3}$ and $k=2$ and got that $F_2(G)=2=n-2$. This is an incorrect example. Since the order of $K_{3,3}$ is 6, it follows that $F_2(G)=2\ne n-2$. They noted that the converse of Proposition 1 is true when $k=1$, but this is not the case for $k\ge 2$. In fact, we are able to get the following stronger result.

Theorem 1

Let G be a graph on n vertices and k be a positive integer with $k\le n-2$. Then $F_k(G)=n-k$ if and only if $G=K_n$.

For $k=n-1$, the result is different from that in the above theorem.

Theorem 2

Let G be a graph on n vertices. Then $F_{n-1}(G)=1$ if and only if G is connected.

In [2], Amos et al. also got the following result for the k-forcing number of G.

Theorem 3

[2] Let k be a positive integer, and let $G=(V,E)$ be a k-connected graph with $n>k$ vertices and $\varDelta \ge 2$. Then, $F_k(G)\le \frac{(\varDelta -2)n+2}{\varDelta +k-2}$, and this inequality is sharp.

By setting $k=1$ in the above theorem, they got the following result.

Corollary 1

[2] Let $G=(V,E)$ be a connected graph with $\varDelta \ge 2$. Then, $Z(G)=F_1(G)\le \frac{(\varDelta -2)n+2}{\varDelta -1}$, and this inequality is sharp.

Corollary 2

[2] Let $G = (V,E)$ be a graph with $\delta \ge 1$. Then, $Z(G)=F_1(G)\le \frac{\varDelta }{\varDelta +1}n$, and this inequality is sharp.

Below Corollary 2, the authors pointed out that equality in Corollary 2 is achieved for a disjoint union of complete graphs of the same order. In fact, we get the following results.

Theorem 4

• (i) Let $G = (V,E)$ be a graph with $\delta \ge 1$. If G is disjoint unions of $\frac{n}{\varDelta +1}$ complete graphs, then $Z(G)=F_1(G)=\frac{\varDelta }{\varDelta +1}n$.

• (ii) Let $G = (V,E)$ be a graph with $\delta \ge 1$. If G is disjoint unions of $\frac{n}{\varDelta +1}$ graphs where at least one such graph is not complete, then $Z(G)=F_1(G)<\frac{\varDelta }{\varDelta +1}n$.

• (iii) Let $G = (V,E)$ be a graph with $\delta \ge 1$. If G is disjoint unions of more than $\frac{n}{\varDelta +1}$ complete graphs, then $Z(G)=F_1(G)<\frac{\varDelta }{\varDelta +1}n$.

Moreover, they posed a conjecture on the zero forcing number of a graph.

Conjecture 1

[2] Let $G=(V,E)$ be a connected graph with $\varDelta \ge 2$. Then, $Z(G)=F_1(G)=\frac{(\varDelta -2)n+2}{\varDelta -1}$ if and only if $G=C_n$, $G=K_{\varDelta +1}$ or $G=K_{\varDelta ,\varDelta }$.

In the last part of this paper, we prove that this conjecture is true. We should remark that in [6], the authors showed that if a graph G satisfies $Z(G)=F_1(G)=\frac{(\varDelta -2)n+2}{\varDelta -1}$, then G is regular, but they did not prove this conjecture.

2 Preliminaries

In this section, we give some results which will be used in the sequel and illustrate the correlation of some known results.

Proposition 2

Let G be a connected graph on n vertices, and let k be a positive integer. Then, $F_k(G)\le n-k$.

Proposition 3

Let G be a graph with $F_k(G)=n-k$ and $V(G)=A\cup B$, where $|A|=n-k-1$, $|B|=k+1$ and $A\cap B=\emptyset$. For each vertex $x\in A$, $d_B(x)=k+1$ or 0.

Proof

Suppose there is a vertex x in A satisfying $1\le d_B(x)\le k$. Initial color A. Then the colored vertex x forces N(x) to be colored. Now, there are at most k remaining vertices uncolored and they can be colored automatically. Thus $F_k(G)\le |A|=n-k-1$, a contradiction. $\square$

In [2], Amos et al. got the following results.

Proposition 4

[2] Let $G=(V,E)$ be a graph.

• (1) If G is connected with $|V(G)|\ge 2$, then $F_{\varDelta }(G)=1$.

• (2) If G is connected with $\varDelta \ge 2$, then $F_{\varDelta -1}(G)\le 2$ with equality holding if and only if G is $\varDelta$-regular.

• (3) If k is a positive integer, then $F_k(G)\ge F_{k+1}(G)$.

In [6], Caro et al. got the following results.

Proposition 5

[6] Let k be a positive integer. If $G=(V, E)$ is a connected graph with maximum degree $\varDelta \le k$, then $F_k(G)=1$.

Theorem 5

[6] Let k be a positive integer, and let $G=(V, E)$ be a connected graph with minimum degree $\delta$ and maximum degree $\varDelta \ge k+1$.

• (i) If $\delta <\varDelta =k+1$, then $F_k(G)=1$.

• (ii) If $\delta =\varDelta =k+1$, then $F_k(G)=2$.

• (iii) Otherwise, if $\varDelta \ge k+2$, then the following inequality holds,

  $$\begin{aligned} F_k(G)\le \frac{(\varDelta -k-1)|V(G)|+\max \{\delta (k+1-\varDelta )+k,k(\delta -\varDelta +2)\}}{\varDelta -1}. \end{aligned}$$

In fact, Proposition 5 coincides to (1) of Proposition 4, (i) and (ii) of Theorem 5 coincide to (2) of Proposition 4.

3 Main Results

In this section, we will give the proof of our main theorems and prove the conjecture.

Proof of Theorem 1

The necessity is verified by Proposition 1.

Now we prove the sufficiency. Let G be a graph with $F_k(G)=n-k$. We claim that G is connected. If not, there are $\ell$ ($\ell \ge 2$) components in G, say $G_1,G_2,\ldots ,G_{\ell }$. By the simple observation that the k-forcing number is addictive component-wise and by Proposition 2, $F_k(G)= \varSigma ^{\ell }_{i=1}F_k(G_i)\le \varSigma ^{\ell }_{i=1}(n_i-k)=n-\ell k< n-k$, a contradiction.

First we deal with the case when $k=n-2$. Suppose that $G\ne K_n$. Then there is a vertex, say x, satisfying that $d(x)\le n-2$. Initially colored x forces N(x) to be colored. Then at most $n-2$ vertices remain uncolored and they can be colored automatically. Then $F_k(G)=1$, a contradiction.

Next we deal with the case when $k\le n-3$. Let $V(G)=A\cup B$, where $A\cap B=\emptyset$ and $|A|=n-k-1$, $|B|=k+1$. Since G is connected, we may suppose there is a vertex x in A with $d_B(x)=k+1$. To get the result, we prove some claims. $\square$

Claim 1

B is a clique.

Proof of Claim 1

Suppose there are two nonadjacent vertices y and z in B. We interchange y and x to get another partition of V(G) into $A'=A\cup \{y\}\setminus \{x\}$ and $B'=B\cup \{x\} \setminus \{y\}$. It is easy to check that $|A'|=n-k-1$ and $|B'|=k+1$. Now in this new partition, the vertex y in $A'$ is adjacent to the vertex x in $B'$, but not to z in $B'$, a contradiction to Proposition 3. $\square$

In fact, we can get a stronger result than that in Proposition 3.

Claim 2

For each vertex $x\in A$, $d_B(x)=|B|=k+1$.

Proof of Claim 2

Since $k\le n-3$, it follows that $n-k-1\ge 2$. We suppose there is another vertex in A, say u, with $d_B(u)=0$. By interchanging a vertex y in B and u, we get a new partition of V(G). Now the vertex y is adjacent to x, but not to u, a contradiction to Proposition 3. $\square$

Claim 3

A is a clique.

Proof of Claim 3

Suppose A is not a clique. Then a vertex in A, say u, is not adjacent to x. we interchange a vertex y in B and x to have another partition of V(G). Since $k\ge 1$, it follows that there are at least two vertices in B. Now u is adjacent to a vertex in B different from y, but not to x, contradicting Proposition 3.

Combining Claims 1,2,3, we have that $G=K_n$. $\square$

Proof of Theorem 2

Let G be a connected graph. Clearly, it follows by Proposition 2 that $F_{n-1}(G)=1$. Conversely, suppose that G is disconnected. Then G has at least two components and then $F_{n-1}(G)\ge 2$, a contradiction. $\square$

Proof of Theorem 4

Let G be a disjoint union of complete graphs $K_{p_1},K_{p_2},\ldots ,K_{p_{\frac{n}{\varDelta +1}}}$. Thus $p_1+p_2+\cdots +p_{\frac{n}{\varDelta +1}}=n$. By Proposition 1, $F_1(G)=(p_1-1)+(p_2-1)+\cdots +(p_{\frac{n}{\varDelta +1}-1)}=n-{\frac{n}{\varDelta +1}}$. Thus the proof of (i) is complete. Since the proofs of (ii) and (iii) are similar to that of (i), we omit them here. $\square$

Proof of Conjecture 1

Let G be a connected graph with $Z(G)=F_1(G)=\frac{(\varDelta -2)n+2}{\varDelta -1}$. Let S be a smallest 1-forcing set with $|S|=\frac{(\varDelta -2)n+2}{\varDelta -1}$. Suppose there are $\ell$ ($\ell \ge 1$) components in $Q=V-S$, say $Q_1,Q_2,\ldots ,Q_{\ell }$. We claim that S is a smallest 1-forcing set of $G[S\cup Q_i]$ for each i with $1\le i\le \ell$. Otherwise, there is a 1-forcing set $S'$ of $G[S\cup Q_i]$ with $|S'|< |S|$ for some i. Initially colored $S'$ forces the remaining vertices of $G[S\cup Q_i]$ to be colored. Now S is colored in G, and the remaining vertices of other components of Q, different from $Q_i$, can be colored since S is a smallest 1-forcing set of G. Thus $S'$ is a 1-forcing set of G smaller than S, contradicting that S is a smallest 1-forcing set of G. $\square$

Now we have that S is a smallest 1-forcing set of $G[S\cup Q_i]$ such that $Q_i$ induces a connected subgraph. From the proof of Theorem 3 in [2], we have the following four facts.

Fact 1 Each vertex in S is adjacent to exactly one vertex of $Q_i$.

Fact 2$e(S,Q_i)=|S|$.

Fact 3$G[Q_i]$ is a tree; namely, $m(G[Q_i])=|Q_i|-1$.

Fact 4 Each vertex in $Q_i$ has the maximum degree in $G[S\cup Q_i]$. Moreover, each vertex in $Q_i$ has $\varDelta$ in G.

If $\varDelta =2$, then $|S|=2$. It follows that $|Q|=n-2$ and there are no more than two components in Q, that is, $\ell \le 2$; otherwise, the degree of a vertex in S may be more than 2 in G. If G[S] is connected, then $\ell =1$. Moreover, by Fact 1 and Fact 4, two vertices of $Q_1$ have degree one in $Q_1$ and other vertices of $Q_1$ have degree two in $Q_1$. It follows by Fact 3 that $Q_1=P_{n-2}$ and each end-vertex is adjacent to one vertex of S, respectively. Therefore, $G=C_n$. If G[S] is disconnected, then $\ell =2$. If not, suppose $\ell =1$. By the same argument, we get that G is $P_n$ and $Z(P_n)=F_1(P_n)=1$, a contradiction. Similarly, both $Q_1$ and $Q_2$ are paths, and each end-vertex of $Q_1$ or $Q_2$ is adjacent to one vertex of S, respectively. We also have that $G=C_n$.

It remains to consider the case that $\varDelta \ge 3$. Solving from $|S|=\frac{(\varDelta -2)n+2}{\varDelta -1}$ for n, we get $n=|S|+\frac{|S|-2}{\varDelta -2}$. Since n is an integer, we may assume that $|S|-2=t(\varDelta -2)$, where t is a positive integer. We divide into three cases.

Case 1$t=1$.

In this case, $|S|=\varDelta$ and $n=\varDelta +1$. By Theorem 1, we have that $G=K_{\varDelta +1}$.

Case 2$t=2$.

In this case, $|S|=2\varDelta -2$, $n=2\varDelta$ and $|Q|=2$. We claim that $\ell =1$. Otherwise, each of $Q_1$ and $Q_2$ is a single vertex. Suppose $Q_1=\{u\}$. By Fact 1, u is adjacent to all vertices in S. Thus, we have $2\varDelta -2=\varDelta$. It follows that $\varDelta =2$, a contradiction. By Fact 3, we may assume that the two adjacent vertices of Q are u and v. By Fact 1, u is adjacent to $\varDelta -1$ vertices in S and v is adjacent to the remaining $\varDelta -1$ vertices in S. Let $A=N(u)\cap S$ and $B=N(v)\cap S$. Thus, $|A|=|B|=\varDelta -1$ and $A\cup B=S$. Next we will claim that each of A and B is an independent set in S, and each vertex in A is adjacent to each vertex in B. Proceeding by contradiction, suppose that A is not an independent set in S. Then there is at least one edge, say $x_1x_2$, in A. Since $x_1$ is adjacent to both u and $x_2$, $d(x_1)\le \varDelta$ and $|B|=\varDelta -1$, we have that there is at least one vertex in B not adjacent to $x_1$, say $y_1$. Let $S'=S-y_1$ be the remaining vertices in S after $y_1$ is taken out. Now applying the 1-forcing process to $S'$. At first, $x_1$ 1-forces u, then u 1-forces v, and then v 1-forces $y_1$. Thus $S'$ is a 1-forcing set. Clearly, $|S'|<|S|$ which contradicts the fact that S is a smallest 1-forcing set. Similarly, each vertex in A is adjacent to each vertex in B, that is, A and B form a complete bipartite graph $G=K_{\varDelta -1,\varDelta -1}$ in S. From the above, $G=K_{\varDelta ,\varDelta }$.

Case 3$t\ge 3$.

For j with $1\le j\le \varDelta$, by Fact 3 and Fact 4, each vertex of degree j in each component $Q_i$ is adjacent to $\varDelta -j$ vertices in S. Denote the number of edges between S and $Q_i$ by $e(S,Q_i)$. Summing up all vertices in $Q_i$, we have $\varSigma _{j=1}^{\varDelta }(\varDelta -j)=e(S,Q_i)=|S|=t(\varDelta -2)+2$. Comparing the left- and right-most expressions in the above equality, and solving for t, we get $t=\frac{\varDelta ^2-\varDelta -4}{2(\varDelta -2)}=\frac{\varDelta +1}{2}-\frac{1}{\varDelta -2}$. As t is an integer, we have that $\varDelta =3$ or 4. If $\varDelta =3$, then $t=1$; if $\varDelta =4$, then $t=2$. It contradicts the precondition $t\ge 3$ in both cases.

From the above arguments, we have that $G=C_n$, $G=K_{\varDelta +1}$ or $G=K_{\varDelta ,\varDelta }$.

Conversely, it is easy to check that if $G=C_n$, $G=K_{\varDelta +1}$ or $G=K_{\varDelta ,\varDelta }$, then $Z(G)=F_1(G)=\frac{(\varDelta -2)n+2}{\varDelta -1}$.

Remark 1

In [2], the authors posed the following problem: characterize the connected graphs with $n\ge 2$ for which, $Z(G)=F_1(G)=n-\gamma _c(G)$, where $\gamma _c(G)$ is the connected domination number. They mentioned that equality holds for $K_n$, $C_n$ and $K_{p,q}$ with $p\ge q\ge 2$. Furthermore, we find another graph $G^*$ constructed by subdividing an edge of $K_{2,3}$. It is easy to check that $F_1(G^*)=3$ and $\gamma _c(G^*)=3$. Thus $Z(G^*)=F_1(G^*)=n-\gamma _c(G^*)$. It is not easy to solve this problem, and we would like to study this problem in the future.