Publication: An intermediate value theorem for the arboricities
1
0
Issued Date
2011
Resource Type
File Type
application/pdf
ISSN
1611712
Other identifier(s)
2-s2.0-80052656856
Rights Holder(s)
มหาวิทยาลัยศรีนครินทรวิโรฒ
Bibliographic Citation
International Journal of Mathematics and Mathematical Sciences. Vol 2011, No. (2011), p.-
Suggested Citation
Punnim N., Chantasartrassmee A. An intermediate value theorem for the arboricities. International Journal of Mathematics and Mathematical Sciences. Vol 2011, No. (2011), p.-. doi:10.1155/2011/947151 Retrieved from: https://hdl.handle.net/20.500.14740/7243
Author(s)
Abstract
Let G be a graph. The vertex (edge) arboricity of G denoted by a (G) (a 1 (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 R (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 R (d) } and y (π) = max (π, d): = m a x {π G): G ∈ R (d) } naturally arise and hence (d): = {π(G): G ∈ R (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 m in (a, rn) in all situations and max (a, rn) for all n > 2 r + 2. © 2011 Avapa Chantasartrassmee and Narong Punnim.