An Intermediate Value Theorem for the Arboricities
Let G 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 R(d) be the class of realizations of d. We prov...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2011/947151 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Let G 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 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):=max{π(G):G∈R(d)} naturally arise and hence π(d):={π(G):G∈R(d)}={z∈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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |