An Intermediate Value Theorem for the Arboricities

Avapa Chantasartrassmee and Narong Punnim

International Journal of Mathematics and Mathematical Sciences, 2011, vol. 2011, 1-7

Abstract:

Let be a graph. The vertex (edge) arboricity of denoted by is the minimum number of subsets into which the vertex (edge) set of can be partitioned so that each subset induces an acyclic subgraph. Let be a graphical sequence and let be the class of realizations of . We prove that if , then there exist integers and such that has a realization with if and only if is an integer satisfying . Thus, for an arbitrary graphical sequence and , the two invariants and   naturally arise and hence We write for the degree sequence of an -regular graph of order . We prove that . We consider the corresponding extremal problem on vertex arboricity and obtain in all situations and for all .

Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2011/947151.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2011/947151.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:947151

DOI: 10.1155/2011/947151

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().