An Intermediate Value Theorem for the Arboricities
Joint Authors
Chantasartrassmee, Avapa
Punnim, Narong
Source
International Journal of Mathematics and Mathematical Sciences
Issue
Vol. 2011, Issue 2011 (31 Dec. 2011), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-06-28
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Chantasartrassmee, Avapa& Punnim, Narong. 2011. An Intermediate Value Theorem for the Arboricities. International Journal of Mathematics and Mathematical Sciences،Vol. 2011, no. 2011, pp.1-7.
https://search.emarefa.net/detail/BIM-510445
Modern Language Association (MLA)
Chantasartrassmee, Avapa& Punnim, Narong. An Intermediate Value Theorem for the Arboricities. International Journal of Mathematics and Mathematical Sciences No. 2011 (2011), pp.1-7.
https://search.emarefa.net/detail/BIM-510445
American Medical Association (AMA)
Chantasartrassmee, Avapa& Punnim, Narong. An Intermediate Value Theorem for the Arboricities. International Journal of Mathematics and Mathematical Sciences. 2011. Vol. 2011, no. 2011, pp.1-7.
https://search.emarefa.net/detail/BIM-510445
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-510445