An excessive factorization of a graph G is a minimum set F of1-factors of G whose union is E(G). In this paper we study excessive factorizations of regular graphs. We introduce two graph parameters related to excessive factorizations and show that their computation is NP-hard. We pose a number of questions regarding these parameters. We show that the size of an excessive factorization of a regular graph can exceed the degree of the graph by an arbitrarily large quantity. We conclude with a conjecture on the excessive factorizations of r-graphs.
Excessive Factorizations of Regular Graphs / Bonisoli, Arrigo; D., Cariolaro. - STAMPA. - (2007), pp. 73-84. (Intervento presentato al convegno Graph Theory in Paris tenutosi a Parigi nel Luglio 2004) [10.1007/978-3-7643-7400-6_7].
Excessive Factorizations of Regular Graphs
BONISOLI, Arrigo;
2007
Abstract
An excessive factorization of a graph G is a minimum set F of1-factors of G whose union is E(G). In this paper we study excessive factorizations of regular graphs. We introduce two graph parameters related to excessive factorizations and show that their computation is NP-hard. We pose a number of questions regarding these parameters. We show that the size of an excessive factorization of a regular graph can exceed the degree of the graph by an arbitrarily large quantity. We conclude with a conjecture on the excessive factorizations of r-graphs.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
