# On thek-Component Independence Number of a Tree

Authors: Shuting Cheng; Baoyindureng Wu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

LetG be a graph and k≥1 be an integer. A subset S of vertices in a graph G is called a k-component independent set of G if each component of GS has order at most k. The k-component independence number, denoted by αckG, is the maximum order of a vertex subset that induces a subgraph with maximum component order at most k. We prove that if a tree T is of order n, then αkT≥k/k+1n. The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum k-component independent set of a tree.


---

## Body

## 1. Introduction

LetG=VG,EG be a graph and k≥1 be an integer and S⊆VG. We use GS to denote the subgraph of G induced by S⊆VG. We call S a k-component independent set of G if each component of GS has order at most k. A k-component independent set is maximum if G contains no larger k-component independent set and maximal if the set cannot be extended to a larger k-component independent set. The k-component independence number, denoted by αckG, is the cardinality of a maximum k-component independent set of G.On the contrary,S⊆VG is called a k-component vertex covering of G if VG∖S is a k-component independent set of G. A k-component vertex covering is minimum if G contains no smaller k-component vertex covering and minimal if the set cannot be contained in a smaller k-component vertex covering. The k-component vertex covering number, denoted by βckG, is the cardinality of a minimum k-component vertex covering of G.By the definition above, for any graphG of order n,(1)αckG+βckG=n,αckG≥αck−1G≥⋯≥αc1G=αG,βckG≤βck−1G≤⋯≤βc1G=βG,where αG and βG are the ordinary independence number and vertex covering number of G.Thek-component chromatic number of a graph G, denoted by χckG, is the smallest number of colours needed in k-component coloring, a coloring of the vertices such that color classes are k-component independent sets. The notations αckG and χckG come from [1]. The notion of k-component coloring is first studied by Kleinberg et al. [2]. It was extensively studied in the past two decades [3–9]. We refer to an excellent survey on this topic [10].A notion, close tok-component vertex covering of a graph, is called the fragmentability of a graph, which was first introduced by Edwards and McDiarmid [11] when they were investigating the harmonious colorings of graphs. It was further studied in [12, 13].Proposition 1.
In general, decidingαckG is NP-hard for a graph G.Proof.
Note that1/kαckG≤αG≤αckG for any graph G. If αckG is determined by polynomial-time algorithm, then αG is determined by at most,(2)∑b=a/kanb,additional check that whether S is an independent set or not, for every S⊆VG with ⌊a/k⌋≤S≤a, where a=αckG, contradicting the folklore that determining αG is NP-hard for a graph G, in general.In this note, we give a linear-time algorithm for finding a maximumk-component independence number of a tree.


## 2. An Lower Bound onαckT for a Tree T

LetG be a graph and x∈VG. The order of G is denoted by vG. We use NGx denote the set of neighbors of a vertex x of G. The degree of x, denoted by dGx, is the number of edges incident with x in G. Furthermore, the two symbols are simply denoted by Nx and dx, respectively. For a subset S of the vertex set VG of G, GS denotes the subgraph of G induced by S.LetT be a tree with root r. The levellx of a vertex x in T is the length of the path rTx. Each vertex on the path rTx is called an ancestor of x, and each vertex of, which v is an ancestor, is a descendant of v. An ancestor or descendant of a vertex is proper if it is not the vertex itself. The immediate proper ancestor of a vertex x∈VT∖r is its predecessor or parent, denoted px. Let Tx denote the subtree of T with the vertex set which consists of the set of descendants of x.Lemma 1.
Letn and k be two integers with n≥k+1≥2.For any treeT of order n, there exists a vertex v such that T−v has dv−1 components, each of which has order at most k, but the sum of their order is at least k.In particular, every nontrivial treeT has a vertex v such that all its neighbors but one are leaves.Proof.
Take a vertexr∈VT as the root of T, thereby px and lx of x are uniquely defined for each x∈VT∖r. Let q=maxlx|x∈VT. Let Vt=x|x∈VT with lx=t, for each t∈0,1,…,q.
Define a weight functionwu=du−1, for each u∈Vq−1. If there is a vertex uq−1∈Vq−1 such that wuq−1≥k, then uq−1 is the vertex, as we desired.
Otherwise,wu≤k−1, for every vertex u∈Vq−1. It follows that T−u has du−1 components, each of which has order at most k for each u∈Vq−2. Define wx:=∑py=xwy+1 for each x∈Vq−2.
If there is a vertexuq−2∈Vq−2 with wuq−2≥k, then uq−2 is the vertex v, as we want. Otherwise, wu≤k−1, for every vertex u∈Vq−2. It follows that T−u has du−1 components, each of which has order at most k, for each u∈Vq−3. Define a weight function wx:=∑py=xwy+1, for each x∈Vq−3.
Repeat the procedure above; sincen≥k+1 is finite, there exists an integer i∈0,1,…,q−1 such that there exists a vertex uq−i∈Vq−i with wuq−i≥k. It can be seen that uq−i is the vertex we required.Theorem 1.
Letk≥1 be an integer. For any tree T of order n, βckT≤n/k+1. Equivalently, αckT≥k/k+1n. The bound is sharp.Proof.
We use induction onn. If n≤k, then βkT=0, and the result trivially holds. Now, assume that n≥k+1. By Lemma 1, there exists a vertex v of T as the assertion in Lemma 1. Let T1,…,Td−1,Td be all components of T−v such that ∑i=1d−1vTi≥k and vTi≤k, for each i∈1,…,d−1, where d=dv. By the induction hypothesis, βkTd≤vTd/k+1. So,(3)βckT≤1+βckTd≤1+vTdk+1≤1+n−k−1k+1=nk+1.
The bound is achieved by the pathPn of order n when n is divisible by k+1.By takingk=⌊n/2⌋ in the above theorem, we have the following.Corollary 1.
(see [14]). For a tree T of order n≥2, βc⌊n/2⌋T=1; equivalently, there exists a vertex v∈VT such that each component of T−v has order at most ⌊n/2⌋.A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. The conflict-free vertex-connection number, denoted byvcfcG, is defined as the smallest number of colours required to make G conflict-free vertex connected. Li et al. [15] conjectured that, for a connected graph G of order n, vcfcG≤vcfcPn. Using Corollary 1, the authors of [14] are able to confirm the above conjecture. We refer to [16–18], for more recent results, on conflict-free vertex-connection of graphs. Next we give a linear time algorithm (Algorithm 1) for finding minimum k-component vertex covering of a tree.Algorithm 1: Algorithm for finding minimum k-component vertex covering.
Input: a treeT with a vertex r as its root.Output: a minimumk-component vertex covering C of T.(1)
C:=∅(2)
whilevT>k, do(3)
setq:=maxlx|x∈VT, S:=x|lx=q−1, wx:=dx−1 for each x∈S(4)
ifS≠∅(5)
choose a vertexx∈S(6)
ifwx≥k, set C:=C∪x, T:=T−Tx go to Step 2(7)
ifwx<k, put wx:=wx+1, and put S:=S∖x, go to Step 4(8)
else(9)
replaceS:=∑y∈Spy(10)
wx:=∑py=xwy for each x∈S, go to Step 4(11)
end if(12)
end while(13)
returnC


## 3. Linear-Time Algorithm

Theorem 2.
EveryC returned by the algorithm is a minimum k-component vertex covering of T.Proof.
We prove it by the induction onvT.
IfvT≤k, C returned by the algorithm is the empty set and thus is a minimum k-component vertex covering of T since βckT=0.
Next, assume thatvG≥k+1. Let C=v1,v2,…,vt, where v1 is the first vertex added to C by the algorithm. By the choice of the algorithm, v1 is a vertex with the property described in the assertion in Lemma 1. Let T1,…,Td−1,Td be all components of T−v1 such that ∑i=1d−1vTi≥k and vTi≤k, for each i∈1,…,d−1, where d=dv1.
By the induction hypothesis,v2,…,vt is a minimum k-component vertex covering of Td. Thus, C is a k-component vertex covering of T.
SupposeC is not a minimum k-component vertex covering of T, and let C∗ be a minimum k-component vertex covering of T. It is clear that v1∉C∗. Note that C∗∗=C∗∩VTd∪v1 is a k-component vertex covering of T. Thus, C∗∩VTd≥v2,…,vt=C−1.
Since∑i=1d−1vTi≥k, C∗∩∪i=1d−1Ti≠∅. It follows that C∗≥1+C∗∩VTd≥t=C, a contradiction.In the execution of the algorithm, each vertexx is explored at most once to check whether wx≥k or not. So, the running time of the algorithm is On.


## 4. Further Research

Zito [19] determined that the greatest number of maximum independent sets of a tree of order n is,(4)2n−3/2,ifn>1is odd,2n−2/2+1,ifnis even.More relevant work can be found in [20–22]. Naturally, one asks the following questions:(1)
What is the largest number of maximum (or maximal)k-component independent sets on a tree of order n?(2)
What is the largest number of maximum (or maximal)k-component independent sets on a (or connected) graph of order n?(3)
What is the largest number of maximum (or maximal)k-component independent sets on a (or connected) graph of order n vertices and m edges?



---

*Source: 5540604-2021-06-07.xml*