Let G be a graph. The vertex (edge) arboricity of G denoted by 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 , 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 , 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 = rⁿ : = (r, r, …, r) for the degree sequence of an r-regular graph of order n. We prove that . We consider the corresponding extremal problem on vertex arboricity and obtain in all situations and for all n ≥ 2r + 2.

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 V_i, 1 ≤ i ≤ k, such that each induced subgraph 〈V_i〉 contains no cycle. The vertex arboricity a(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, 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, . . Also if r = 1 or s = 1 and otherwise. It is clear that, for every graph G of order n, . We now turn to the second decomposition problem. The edge arboricity or simply the arboricity 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 .

A linear 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 (d₁, d₂, …, d_n) of nonnegative integers is called a degree sequence of a graph G if the vertices of G can be labeled v₁, v₂, …, v_n so that deg v_i = d_i for all i. If a sequence d = (d₁, d₂, …, d_n) 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 deg v = r for each vertex v of G. Such graphs are called r-regular. We write d = rⁿ 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(mod 2). Furthermore, there exists a disconnected r-regular graph of order n if and only if n ≥ 2r + 2.

Let G be a graph and ab, cd ∈ E(G) be independent where ac, bd ∉ E(G). Put

(1.1)

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 G₁ and G₂ are any two realizations of d, then G₂ can be obtained from G₁ 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. Let d be a graphical sequence. Then, the graph ℛ(d) is connected.

Let

and d be a graphical sequence. Put

(1.2)

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 , then (π, ℛ(d))∈IVT.

Theorem 1.2. Let d be a graphical sequence and . 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 Theorem 1.2 follows from Theorem 1.1 and the following results.

Lemma 1.3. Let and σ be a switching on a graph G. Then, π(G^σ) ≤ π(G) + 1.

Proof. Let G be a graph and σ = σ(a, b; c, d) be a switching on G. Then, and hence . Since ac, bd ∈ E(G^σ), we have that and hence .

Let π ∈ {a, a₁}. 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 , where σ⁻¹ = σ(a, c; b, d).

We have the following corollary.

Corollary 1.4. Let G be a graph and let σ be a switching on G. If , then |π(G) − π(G^σ)| ≤ 1.

2. Extremal Results

Let . 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 graph G, , where the maximum is taken over all nontrivial induced subgraphs H of G.

As a consequence of the theorem, it follows that and .

If 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 = (d₁, d₂, …, d_n) (d₁ ≥ d₂ ≥ ⋯≥d_n), then G can be embedded as an induced subgraph of a d₁-regular graph H and π(G) ≤ π(H). Thus, it is reasonable to determine min (π, d) and max (π, d) in the case where d = rⁿ. It should be noted that if r ∈ {0,1}, then for all G ∈ ℛ(rⁿ). Therefore, we may assume from now on that r ≥ 2.

Theorem 2.2. .

Proof. Let G be an r-regular graph of order n. By Theorem 2.1, we see that for any r-regular graph G of order n. Since nr/(2(n − 1)) = r/2 + r/(2(n − 1)), it follows that . 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 . It is clear that |E(H)|/(|V(H)| − 1) ≤ (r + 1)/2. Thus, . Therefore, .

In order to obtain the corresponding extremal results on vertex arboricity, we need to introduce some notation on graph construction.

Let X 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 G₁ and G₂ are disjoint (i.e., V(G₁)∩V(G₂) = ∅), then G₁*G₂ = G₁ ∪ G₂. We also use pG for the union of p disjoint copies of G.

It should be noted once again that an r-regular graph G of order n have if and only if r ∈ {0,1}. Thus, if and only if r ∈ {0,1}. Moreover, .

Let r and n be integers with r ≥ 3 and ℛ(rⁿ) ≠ ∅. Then,

(1)
if n is even and n ≥ 2r, then there exists an r-regular bipartite graph G of order n. Therefore, ;
(2)
if n 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 ;
(3)
if n is even and n = 2(r − 1), then K_r−1,r−1 is the complete (r − 1)-regular bipartite graph of order n. Let X = {x₁, x₂, …, x_r−1} and Y = {y₁, y₂, …, y_r−1} be the corresponding partite sets of K_r−1,r−1. Let G be defined by G = (K_r−1,r−1 − {x₂y₂, x₃y₃, …, x_r−2y_r−2})+{x₁x₂, x₂x₃, …, x_r−2x_r−1, y₁y₂, y₂y₃, …, y_r−2y_r−1}. Then G is an r-regular graph of order n having ;
(4)
if n = 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) + E₁, where E₁ = {ux₁, uy₁, ux₂, uy₂, …, ux_r/2, uy_r/2}, is a graph of order 2r − 1 having r + 1 vertices of degree r and r − 2 vertices of degree r − 1. Put X₁ = {x_i ∈ X : r/2 < i ≤ r − 1} and Y₁ = {y_i ∈ Y : r/2 < i ≤ r − 1}. Thus, |X₁ | = |Y₁ | = (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 X₁ and Y₁. This construction yields .

Case 2. If (r − 2)/2 is odd, then H − x_r/2y_r/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 − x_r/2y_r/2 by adding appropriate independent edges so that .

With these observations, we easily obtain the following result.

Lemma 2.3. .

In order to obtain

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

. That is,

(2.1)

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 ∈ ℛ(r^r+s),
(2)
there exists a graph H ∈ ℛ(r^r+s) such that .

With these observations, we have the following result.

Lemma 2.4. If 1 ≤ s ≤ r − 3, then .

It is well known that . Thus, . It is also well known that G = K_r+2 − F, where F is a 1-factor of K_r+2, is the unique r-regular graph of order r + 2. Since , it follows that a subgraph of induced by any four vertices of contains at most two edges. Equivalently, a subgraph of G induced by any four vertices must contain a cycle. Thus, . It is easy to show that . Thus, .

Let T_n,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 T_n,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, T_n,q is an (n − x)-regular graph if and only if y = 0. If y > 0, then T_n,q contains y(x + 1) vertices of degree n − x − 1 and (q − y)x vertices of degree n − x. A little modification of T_n,q yields a regular graph with prescribed arboricity number as in the following theorem.

Theorem 2.5. Let n, 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 if x is odd,
(2)
there exists an (n − x)-regular graph G of order n such that if x and y are even,
(3)
there exists an (n − x − 1)-regular graph H of order n such that if x is even and y is odd.

Proof. Note that T_n,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 V₁, V₂, …, V_y be partite sets of T_n,q of cardinality x + 1 and U₁, U₂, …, U_q−y be partite sets of T_n,q of cardinality x. It is clear that if v ∈ V₁ ∪ V₂ ∪ ⋯∪V_y and if u ∈ U₁ ∪ U₂ ∪ ⋯∪U_q−y. For each i = 1,2, …y, let V_i = {v_i1, v_i2, …, v_i(x+1)}; similarly, for each j = 1,2, …, q − y, let U_j = {u_j1, u_j2, …, u_jx}.

(1) Suppose that x is odd. Since |V_i | = x + 1 for each i = 1,2, …, y, an (n − x)-regular graph G can be obtained from T_n,q by adding (x + 1)/2 independent edges to each V_i, 1 ≤ i ≤ y. It is clear that .

(2) Suppose that x and y are even. Let where P(V_i) is a path with V_i as its vertex set and E_i = {v_ikv_i(k+1) : 1 ≤ k ≤ x} as its edge set. Let F₁, F₂, …, F_y/2 be defined by F_k = {v_ktv_(k+y/2)t : 2 ≤ t ≤ x} and put . Finally, we obtain a graph G = (T_n,q − F)*H which is an (n − x)-regular graph of order n and .

(3) Suppose that x is even and y is odd. Then, n = qx + y is odd. If q − y ≥ 2, then, by Dirac [10], a subgraph of T_n,q induced by U₁ ∪ U₂ ∪ ⋯∪U_q−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 = T_n,q − F is an (n − x − 1)-regular graph of order n and .

Suppose that q − y = 1. Let F₁ = {v₁₁u₁₁, v₁₂u₁₂, …, v_1xu_1x} and F₂ = {v₁₁v₁₂, v₁₃v₁₄, …, v_1(x−1)v_1x}. Then, H = (T_n,q − F₁) + F₂ is an (n − x − 1)-regular graph of order n and .

Note that if G 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. Let r and s be integers with r ≥ 3 and 1 ≤ s ≤ r − 3. Then,

(2.2)

Proof. By Lemma 2.4, we have that if 1 ≤ s ≤ r − 3. We have already shown that 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 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 that T_n,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 T_n,q by adding (s + 1)/2 independent edges to each partite set. Then, G is an r-regular graph of order n having .

If s 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 T_n,q with .

Now suppose that y > 0 and therefore x ≤ s. Thus, T_r+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 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 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. If x 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 . Since x ≤ s, it follows that r + s − x ≥ r. If s − x = 0, then G ∈ ℛ(r^r+s) with , 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 , as required.

Suppose s − 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 . Since s − x − 1 is even, the result follows by the same argument as above.

Case 2. If x 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 . 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 graph G, , where the maximum is taking over all induced subgraphs G^′ of G. In particular, if G is an r-regular graph.

In general, the bound given in Theorem 2.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. For .

Proof. The result follows easily if r ∈ {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)K_r+1 ∪ H, where H is an r-regular graph of order r + t + 1. Since and , it follows that .

Acknowledgments

The first author would like to thank University of the Thai Chamber of Commerce for financial support. The second author gratefully acknowledges the financial support provided by the Thailand Research Fund through the Grant number BRG5280015. The authors wish to thank the referee for useful suggestions and comments that led to an improvement of this paper.

References

1 Chartrand G. and Lesniak L., Graphs & Digraphs, 2005, 4th edition, Chapman & Hall/CRC, London, UK, 2107429.
Google Scholar
2 Chartrand G., Geller D., and Hedetniemi S., Graphs with forbidden subgraphs, Journal of Combinatorial Theory. (1971) 10, 12–41, 0285427.
10.1016/0095-8956(71)90065-7
Google Scholar
3 Nash-Williams St. J. A., Decomposition of finite graphs into forests, Journal of the London Mathematical Society. (1964) 39, 0161333.
Google Scholar
4 Harary F., Covering and packing in graphs. I, Annals of the New York Academy of Sciences. (1970) 175, 198–205, 0263677.
10.1111/j.1749-6632.1970.tb56470.x
Web of Science® Google Scholar
5 Akiyama J., Exoo G., and Harary F., Covering and packing in graphs. III: cyclic and acyclic invariants, Mathematica Slovaca. (1980) 30, no. 4, 405–417, 595302.
Google Scholar
6 Havel V., A remark on the existence of finite graphs (Czech), Časopispest Mathematical Journal. (1955) 80, 477–480.
Google Scholar
7 Hakimi S. L., On realizability of a set of integers as degrees of the vertices of a linear graph, SIAM Journal on Applied Mathematics. (1962) 10, 496–506, 0148049.
10.1137/0110037
Web of Science® Google Scholar
8 Eggleton R. B. and Holton D. A., Graphic sequences, combinatorial mathematics, VI, 748, Proceedings of the 6th Australian Conference, 1978, Armidale, Australia, University of New England, 1–10, Lecture Notes in Math..
Google Scholar
9 Punnim N., Decycling regular graphs, The Australasian Journal of Combinatorics. (2005) 32, 147–162, 2139804.
Google Scholar
10 Dirac G. A., Some theorems on abstract graphs, Proceedings of the London Mathematical Society. (1952) 2, 69–81, 0047308.
10.1112/plms/s3-2.1.69
Google Scholar
11 Chartrand G. and Kronk H. V., The point-arboricity of planar graphs, Journal of the London Mathematical Society. (1969) 44, 612–616, 0239996.
10.1112/jlms/s1-44.1.612
Web of Science® Google Scholar

All articles

An Intermediate Value Theorem for the Arboricities

Abstract

1. Introduction

2. Extremal Results

Acknowledgments

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

An Intermediate Value Theorem for the Arboricities

Abstract

1. Introduction

2. Extremal Results

Acknowledgments

References

References

Related

Information