# An Intermediate Value Theorem for the Arboricities

Authors: Avapa Chantasartrassmee; Narong Punnim
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

LetG be a graph. The vertex (edge) arboricity of G denoted by a(G)(a1(G)) is the minimum number of subsets into which the vertex (edge) set of G can be partitioned so that each subset induces an acyclic subgraph. Let d be a graphical sequence and let ℛ(d) be the class of realizations of d. We prove that if π∈{a,a1}, then there exist integers x(π) and y(π) such that d has a realization G with π(G)=z if and only if z is an integer satisfying x(π)≤z≤y(π). Thus, for an arbitrary graphical sequence d and π∈{a,a1}, the two invariants x(π)=min(π,d):=min{π(G):G∈ℛ(d)} and  y(π)=max(π,d):=max{π(G):G∈ℛ(d)} naturally arise and hence π(d):={π(G):G∈ℛ(d)}={z∈ℤ:x(π)≤z≤y(π)}. We write d=rn:=(r,r,…,r) for the degree sequence of an r-regular graph of order n. We prove that a1(rn)={⌈(r+1)/2⌉}. We consider the corresponding extremal problem on vertex arboricity and obtain min(a,rn) in all situations and max(a,rn) for all n≥2r+2.


---

## Body

## 1. Introduction

We limit our discussion to graphs that are simple and finite. For the most part, our notation and terminology follows that of Chartrand and Lesniak [1]. A typical problem in graph theory deals with decomposition of a graph into various subgraphs possessing some prescribed property. There are ordinarily two problems of this type, one dealing with a decomposition of the vertex set and the other with a decomposition of the edge set. The vertex coloring problem is an example of vertex decomposition while the edge coloring problem is an example of edge decomposition with some additional property. For a graph G, it is always possible to partition V(G) into subsets Vi,1≤i≤k, such that each induced subgraph 〈Vi〉 contains no cycle. The vertex arboricitya(G) of a graph G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces an acyclic subgraph. Thus, a(G)=1 if and only if G is a forest. The vertex arboricity was first defined in [2] by Chartrand et al. For a few classes of graphs, the vertex arboricity is easily determined. For example, a(Cn)=2. a(Kn)=⌈n/2⌉. Also a(Kr,s)=1 if r=1 or s=1 and a(Kr,s)=2 otherwise. It is clear that, for every graph G of order n, a(G)≤⌈n/2⌉. We now turn to the second decomposition problem. The edge arboricity or simply the arboricitya1(G) of a nonempty graph G is the minimum number of subsets into which E(G) can be partitioned so that each subset induces an acyclic subgraph. The arboricity was first defined by Nash-Williams in [3]. As with vertex arboricity, a nonempty graph has arboricity 1 if and only if it is a forest. Also a1(Kn)=⌈n/2⌉.Alinear forest of a graph G is a forest of G in which each component is a path. The linear arboricity is the minimum number of subsets into which E(G) can be partitioned so that each subset induces a linear forest. It was first introduced by Harary in [4] and is denoted by Ξ(G). Note that the Greek letter, capital, Xi, looks like three paths! It was proved in [5] that Ξ(G)=2 for all cubic graphs G and Ξ(G)=3 for all 4-regular graphs G. It was conjectured that Ξ(G)=⌈(r+1)/2⌉ for all r-regular graphs G.A sequence(d1,d2,…,dn) of nonnegative integers is called a degree sequence of a graph G if the vertices of G can be labeled v1,v2,…,vn so that degvi=di for all i. If a sequence d=(d1,d2,…,dn) of nonnegative integers is a degree sequence of some graph G, then d is called graphical sequence. In this case, G is called a realization of d. A graph G is regular of degree r if degv=r for each vertex v of G. Such graphs are called  r-regular. We write d=rn for the sequence (r,r,…,r) of length n, where r is a nonnegative integer and n is a positive integer. It is well known that an r-regular graph of order n exists if and only if n≥r+1 and nr≡0(mod2). Furthermore, there exists a disconnected r-regular graph of order n if and only if n≥2r+2.LetG be a graph and ab,cd∈E(G) be independent where ac,bd∉E(G). Put(1.1)Gσ(a,b;c,d)=(G-{ab,cd})+{ac,bd}.The operationσ(a,b;c,d) is called a switching operation. It is easy to see that the graph obtained from G by a switching has the same degree sequence as G.Havel [6] and Hakimi [7] independently obtained that if G1 and G2 are any two realizations of d, then G2 can be obtained from G1 by a finite sequence of switchings. Let ℛ(d) denote the set of all realizations of degree sequence d. As a consequence of this result, Eggleton and Holton [8] defined, in 1978, the graphℛ(d) of realizations of d whose vertex set is the set ℛ(d), two vertices being adjacent in the graph ℛ(d) if one can be obtained from the other by a switching. As a consequence of Havel and Hakimi, we have the following theorem.Theorem 1.1.
Letd be a graphical sequence. Then, the graph ℛ(d) is connected.Letπ∈{a,a1} and d be a graphical sequence. Put (1.2)π(d)∶={π(G):G∈R(d)}.A graph parameterπ is said to satisfy an intermediate value theorem over a class of graphs𝒥 if G,H∈𝒥 with π(G)<π(H), then, for every integer k with π(G)≤k≤π(H), there is a graph K∈𝒥 such that π(K)=k. If a graph parameter π satisfies an intermediate value theorem over 𝒥, then we write (π,𝒥)∈IVT. The main purpose of this section is to prove that if π∈{a,a1}, then (π,ℛ(d))∈IVT.Theorem 1.2.
Letd be a graphical sequence and π∈{a,a1}. Then, there exist integers x(π) and y(π) such that there exists a graph G∈ℛ(d) with π(G)=z if and only if z is an integer satisfying x(π)≤z≤y(π). That is, π(d)={z∈ℤ:x(π)≤z≤y(π)}.The proof of Theorem1.2 follows from Theorem 1.1 and the following results.Lemma 1.3.
Letπ∈{a,a1} and σ be a switching on a graph G. Then, π(Gσ)≤π(G)+1.Proof.
LetG be a graph and σ=σ(a,b;c,d) be a switching on G. Then, a(Gσ-{a,b})≤a(G) and hence a(Gσ)≤a(Gσ-{a,b})+1≤a(G)+1. Since ac,bd∈E(Gσ), we have that a1(Gσ-{ac,bd})≤a1(G) and hence a1(Gσ)≤a1(Gσ-{ac,bd})+1≤a1(G)+1.Letπ∈{a,a1}. By Lemma 1.3, if π(G)≤π(Gσ), then we have that π(G)≤π(Gσ)≤π(G)+1. If π(G)≥π(Gσ), then, by Lemma 1.3, we see that π(G)=π((Gσ)σ-1)≤π(Gσ)+1≤π(G)+1, where σ-1=σ(a,c;b,d).We have the following corollary.Corollary 1.4.
LetG be a graph and let σ be a switching on G. If π∈{a,a1}, then |π(G)-π(Gσ)|≤1.


## 2. Extremal Results

Letπ∈{a,a1}. By Theorem 1.2, π(d) is uniquely determined by x(π) and y(π), thus it is reasonable to denote x(π)=min(π,d):=min{π(G):G∈ℛ(d)} and y(π)=max(π,d)∶=max{π(G):G∈ℛ(d)}. We first state a famous result on edge arboricity of Nash-Williams [3].Theorem 2.1.
For every nonempty graphG, a1(G)=max⌈|E(H)|/(|V(H)|-1)⌉, where the maximum is taken over all nontrivial induced subgraphs H of G.As a consequence of the theorem, it follows thata1(Kn)=⌈n/2⌉ and a1(Kr,s)=⌈rs/(r+s-1)⌉.Ifπ∈{a,a1} and H is a subgraph of G, then π(H)≤π(G). It is well known that if G is a graph with a degree sequence d=(d1,d2,…,dn)(d1≥d2≥⋯≥dn), then G can be embedded as an induced subgraph of a d1-regular graph H and π(G)≤π(H). Thus, it is reasonable to determine min(π,d) and max(π,d) in the case where d=rn. It should be noted that if r∈{0,1}, then a1(G)=1 for all G∈ℛ(rn). Therefore, we may assume from now on that r≥2.Theorem 2.2.
min(a1,rn)=max(a1,rn)=⌈(r+1)/2⌉.Proof.
LetG be an r-regular graph of order n. By Theorem 2.1, we see that a1(G)≥⌈nr/(2(n-1))⌉ for any r-regular graph G of order n. Since nr/(2(n-1))=r/2+r/(2(n-1)), it follows that a1(G)≥⌈(r+1)/2⌉. Let H be an induced subgraph of G of order m. If m≥r+1, then |E(H)|/(|V(H)|-1)≤mr/(2(m-1)). It follows that |E(H)|/(|V(H)|-1)≤(r+1)/2. If m≤r, then |E(H)|≤(m2). It is clear that |E(H)|/(|V(H)|-1)≤(r+1)/2. Thus, a1(G)≤(r+1)/2. Therefore, min(a1,rn)=max(a1,rn)=⌈(r+1)/2⌉.In order to obtain the corresponding extremal results on vertex arboricity, we need to introduce some notation on graph construction.LetX and Y be finite nonempty sets. We denote by K(X,Y) the complete bipartite graph with partite sets X and Y. Let G and H be any two graphs. Then, G*H is the graph with V(G*H)=V(G)∪V(H) and E(G*H)=E(G)∪E(H). It is clear that the binary operation “*” is associative. If G1 and G2 are disjoint (i.e., V(G1)∩V(G2)=∅), then G1*G2=G1∪G2. We also use pG for the union of p disjoint copies of G.It should be noted once again that anr-regular graph G of order n have a(G)=1 if and only if r∈{0,1}. Thus, min(a,rn)=max(a,rn)=1 if and only if r∈{0,1}. Moreover, min(a,2n)=max(a,2n)=2.Letr and n be integers with r≥3 and ℛ(rn)≠∅. Then,  (1)
ifn is even and n≥2r, then there exists an r-regular bipartite graph G of order n. Therefore, a(G)=2;(2)
ifn is odd and n≥2r+1, then r is even and there exists an r-regular bipartite graph H of order n-1. Let F be a set of r/2 independent edges of H. Then, H-F is a bipartite graph of order n having r vertices of degree r-1 and n-1-r vertices of degree r. Let G be a graph obtained from H-F by joining the r vertices of H-F to a new vertex. Therefore, G is an r-regular graph of order n having a(G)=2;(3)
ifn is even and n=2(r-1), then Kr-1,r-1 is the complete (r-1)-regular bipartite graph of order n. Let X={x1,x2,…,xr-1} and Y={y1,y2,…,yr-1} be the corresponding partite sets of Kr-1,r-1. Let G be defined by G=(Kr-1,r-1-{x2y2,x3y3,…,xr-2yr-2})+{x1x2,x2x3,…,xr-2xr-1,y1y2,y2y3,…,yr-2yr-1}. Then G is an r-regular graph of order n having a(G)=2;(4)
ifn=2r-1, then r is even. Let X and Y be as described in the previous case and u be a new vertex. Then, H=K(X,Y)+E1, where E1={ux1,uy1,ux2,uy2,…,uxr/2,uyr/2}, is a graph of order 2r-1 having r+1 vertices of degree r and r-2 vertices of degree r-1. Put X1={xi∈X:r/2<i≤r-1} and Y1={yi∈Y:r/2<i≤r-1}. Thus, |X1|=|Y1|=(r-2)/2.Case 1.
If(r-2)/2 is even, then we can construct an r-regular graph G from H by adding (r-2)/4 independent edges to each of X1 and Y1. This construction yields a(G)=2.Case 2.
If(r-2)/2 is odd, then H-xr/2yr/2 is a graph having r-1 vertices of degree r and r vertices of degree r-1. Thus, it has r/2 vertices of degree r-1 in X and also r/2 vertices in Y. Since r/2 is even, we can easily construct an r-regular graph G from H-xr/2yr/2 by adding appropriate independent edges so that a(G)=2.With these observations, we easily obtain the following result.Lemma 2.3.
min(a,rn)=2foralln≥2r-2.In order to obtainmin(a,rn) in all other cases, we first state some known result concerning the forest number of regular graphs. Let G be a graph and F⊆V(G). F is called an induced forest of G if the subgraph 〈F〉 of G contains no cycle. The maximum cardinality of an induced forest of a graph G is called the forest number of G and is denoted by f(G). That is,(2.1)f(G)∶=max⁡{|F|:FisaninducedforestofG}.The second author proved in [9] the following result: Let r and s be integers with 1≤s≤r. Then,  (1)
f(G)≤s+1 for all G∈ℛ(rr+s),(2)
there exists a graphH∈ℛ(rr+s) such that f(H)=s+1.With these observations, we have the following result.Lemma 2.4.
If1≤s≤r-3, then min(a,rr+s)≥⌈(r+s)/(s+1)⌉.It is well known thata(Kr+1)=⌈(r+1)/2⌉. Thus, min(a,rr+1)=max(a,rr+1)=⌈(r+1)/2⌉. It is also well known that G=Kr+2-F, where F is a 1-factor of Kr+2, is the unique r-regular graph of order r+2. Since E(G¯)=F, it follows that a subgraph of G¯ induced by any four vertices of V(G¯) contains at most two edges. Equivalently, a subgraph of G induced by any four vertices must contain a cycle. Thus, a(G)≥⌈(r+2)/3⌉. It is easy to show that a(G)=⌈(r+2)/3⌉. Thus, min(a,rr+2)=max(a,rr+2)=⌈(r+2)/3⌉.LetTn,q be the Turán graph of order n containing no clique of order q+1. Thus, there exists a unique pair of integers x and y such that n=qx+y,0≤y<q. Note that Tn,q is a complete q-partite graph of order n consisting of y partite sets of cardinality x+1 and q-y partite sets of cardinality x. Therefore, Tn,q is an (n-x)-regular graph if and only if y=0. If y>0, then Tn,q contains y(x+1) vertices of degree n-x-1 and (q-y)x vertices of degree n-x. A little modification of Tn,q yields a regular graph with prescribed arboricity number as in the following theorem.Theorem 2.5.
Letn,x,q, and y be positive integers satisfying n=qx+y,0<y<q. Then,
(1)
there exists an(n-x)-regular graph G of order n such that a(G)≤q if x is odd,(2)
there exists an(n-x)-regular graph G of order n such that a(G)≤q if x and y are even,(3)
there exists an(n-x-1)-regular graph H of order n such that a(G)≤q if x is even and y is odd.Proof.
Note thatTn,q is a complete q-partite graph of order n consisting of y partite sets of cardinality x+1 and q-y partite sets of cardinality x. Let V1,V2,…,Vy be partite sets of Tn,q of cardinality x+1 and U1,U2,…,Uq-y be partite sets of Tn,q of cardinality x. It is clear that degTn,qv=n-x-1 if v∈V1∪V2∪⋯∪Vy and degTn,qu=n-x if u∈U1∪U2∪⋯∪Uq-y. For each i=1,2,…y, let Vi={vi1,vi2,…,vi(x+1)}; similarly, for each j=1,2,…,q-y, let Uj={uj1,uj2,…,ujx}.
(1) Suppose thatx is odd. Since |Vi|=x+1 for each i=1,2,…,y, an (n-x)-regular graph G can be obtained from Tn,q by adding (x+1)/2 independent edges to each Vi,1≤i≤y. It is clear that a(G)≤q.
(2) Suppose thatx and y are even. Let H=⋃i=1yP(Vi) where P(Vi) is a path with Vi as its vertex set and Ei={vikvi(k+1):1≤k≤x} as its edge set. Let F1,F2,…,Fy/2 be defined by Fk={vktv(k+y/2)t:2≤t≤x} and put F=⋃k=1y/2Fk. Finally, we obtain a graph G=(Tn,q-F)*H which is an (n-x)-regular graph of order n and a(G)≤q.
(3) Suppose thatx is even and y is odd. Then, n=qx+y is odd. If q-y≥2, then, by Dirac [10], a subgraph of Tn,q induced by U1∪U2∪⋯∪Uq-y contains a Hamiltonian cycle C. Since x is even and C is of order x(q-y), it follows that C is of even order. Let F be a set of x(q-y)/2 independent edges of C. Then, H=Tn,q-F is an (n-x-1)-regular graph of order n and a(H)≤q.
Suppose thatq-y=1. Let F1={v11u11,v12u12,…,v1xu1x} and F2={v11v12,v13v14,…,v1(x-1)v1x}. Then, H=(Tn,q-F1)+F2 is an (n-x-1)-regular graph of order n and a(H)≤q.Note that ifG is an r-regular graph on r+s vertices where 1≤s≤r, then r≥(r+s)/2. It follows, by Dirac [10], that G is Hamiltonian.Theorem 2.6.
Letr and s be integers with r≥3 and 1≤s≤r-3. Then,
(2.2)min⁡(a,rr+s)=⌈r+ss+1⌉.Proof.
By Lemma2.4, we have that min(a,rr+s)≥⌈(r+s)/(s+1)⌉ if 1≤s≤r-3. We have already shown that min(a,rr+s)=⌈(r+s)/(s+1)⌉ if s∈{1,2}. Thus, in order to prove this theorem, it suffices to construct an r-regular graph G of order r+s such that a(G)≤⌈(r+s)/(s+1)⌉ for r≥3 and 3≤s≤r-3. Suppose that 3≤s≤r-3. Let q=⌈(r+s)/(s+1)⌉ and put r+s=qx+y,0≤y≤q-1. Then, x≤s+1 and x=s+1 if and only if y=0 and r+s is a multiple of s+1.
Note thatTn,q is a complete q-partite graph of order n consisting of q partite sets of cardinality s+1. Suppose that s is odd. Let G be a graph obtained from Tn,q by adding (s+1)/2 independent edges to each partite set. Then, G is an r-regular graph of order n having a(G)=q.
Ifs is even, then q is even. By the same argument with 2 in Theorem 2.5, there exists an r-regular graph G obtained from Tn,q with a(G)=q.
Now suppose thaty>0 and therefore x≤s. Thus, Tr+s,q contains y partite sets of cardinality x+1 and q-y partite sets of cardinality x. By Theorem 2.5, there exists an (r+s-x)-regular graph G of order r+s with a(G)≤q if x is odd or both x and y are even and there exists an (r+s-x-1)-regular graph H of order r+s with a(H)≤q if x is even and y is odd. Since x≤s, it follows that r+s-x≥r. We will consider two cases according to the parity of x and y as in Theorem 2.5.
Case 1.
Ifx is odd or both x and y are even, then, by Theorem 2.5, there exists an (r+s-x)-regular graph G of order r+s with a(G)≤q. Since x≤s, it follows that r+s-x≥r. If s-x=0, then G∈ℛ(rr+s) with a(G)≤q, as required. Suppose that s-x is even and s-x≥2. By Dirac [10], G contains enough edge-disjoint Hamiltonian cycles whose removal produces an r-regular graph G′ of order r+s and a(G′)≤a(G)≤q, as required.
Supposes-x is odd. Then, either r+s-x or r is odd and therefore r+s is even. Also by Dirac [10], G contains a 1-factor F where G-F is an (r+s-x-1)-regular graph and a(G-F)≤a(G)≤q. Since s-x-1 is even, the result follows by the same argument as above.
Case 2.
Ifx is even and y is odd, then, by Theorem 2.5, there exists an (r+s-x-1)-regular graph H of order r+s and a(H)≤q. Since r+s=qx+y is odd, it follows that both r+s-x-1 and r are even. Since x≤s, it follows that r+s-x-1≥r-1. Therefore, it follows by the parity that r+s-x-1≥r. The result follows easily by the same argument as in Case 1.
This completes the proof.Chartrand and Kronk [11] obtained a good upper bound for the vertex arboricity. In particular, they proved the following theorem.Theorem 2.7.
For each graphG, a(G)≤1+⌊maxδ(G′)/2⌋, where the maximum is taking over all induced subgraphs G′ of G. In particular, a(G)≤1+⌊r/2⌋ if G is an r-regular graph.In general, the bound given in Theorem2.7 is not sharp but it is sharp in the class of r-regular graphs of order n≥2r+2 as we will prove in the next theorem.Theorem 2.8.
Forn≥2r+2,max(a,rn)=1+⌊r/2⌋.Proof.
The result follows easily ifr∈{0,1,2}. Suppose that r≥3. We write n=(r+1)q+t,0≤t≤r. Thus, q≥2. Note that an r-regular graph of order n exists implying rn must be even. Thus, if r is odd, then n must be even and hence t must be even. Put G=(q-1)Kr+1∪H, where H is an r-regular graph of order r+t+1. Since a(Kr+1)=⌈(r+1)/2⌉=1+⌊r/2⌋ and a(H)≤1+⌊r/2⌋, it follows that a(G)=1+⌊r/2⌋.



---

*Source: 947151-2011-06-28.xml*