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!
|
| _version_ | 1832564406726164480 |
|---|---|
| author | Avapa Chantasartrassmee Narong Punnim |
| author_facet | Avapa Chantasartrassmee Narong Punnim |
| author_sort | Avapa Chantasartrassmee |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-65381814bf2e4d2a9afb97d875837cfb |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2011-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-65381814bf2e4d2a9afb97d875837cfb2025-02-03T01:11:01ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252011-01-01201110.1155/2011/947151947151An Intermediate Value Theorem for the ArboricitiesAvapa Chantasartrassmee0Narong Punnim1Department of Mathematics, School of Science, University of the Thai Chamber of Commerce, Bangkok 10400, ThailandDepartment of Mathematics, Srinakharinwirot University, Sukhumvit 23, Bangkok 10110, ThailandLet 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.http://dx.doi.org/10.1155/2011/947151 |
| spellingShingle | Avapa Chantasartrassmee Narong Punnim An Intermediate Value Theorem for the Arboricities International Journal of Mathematics and Mathematical Sciences |
| title | An Intermediate Value Theorem for the Arboricities |
| title_full | An Intermediate Value Theorem for the Arboricities |
| title_fullStr | An Intermediate Value Theorem for the Arboricities |
| title_full_unstemmed | An Intermediate Value Theorem for the Arboricities |
| title_short | An Intermediate Value Theorem for the Arboricities |
| title_sort | intermediate value theorem for the arboricities |
| url | http://dx.doi.org/10.1155/2011/947151 |
| work_keys_str_mv | AT avapachantasartrassmee anintermediatevaluetheoremforthearboricities AT narongpunnim anintermediatevaluetheoremforthearboricities AT avapachantasartrassmee intermediatevaluetheoremforthearboricities AT narongpunnim intermediatevaluetheoremforthearboricities |