Let m be a positive integer and let G be a cubic graph of order 2n. Weconsider the problem of covering the edge-set of G with the minimumnumber of matchings of size m. This number is called excessive [m]-indexof G in the literature. The case m = n, that is a covering with perfectmatchings, is known to be strictly related to an outstanding conjectureof Berge and Fulkerson. In this paper we study in some details the casem = n-1. We show how this parameter can be large for cubic graphswith low connectivity and we furnish some evidence that each cyclically4-connected cubic graph of order 2n has excessive [n-1]-index at most 4.Finally, we discuss the relation between excessive [n-1]-index and someother graph parameters such as oddness and circumference.
Covering cubic graphs with matchings of large size
Mazzuoccolo, Giuseppe
2013-01-01
Abstract
Let m be a positive integer and let G be a cubic graph of order 2n. Weconsider the problem of covering the edge-set of G with the minimumnumber of matchings of size m. This number is called excessive [m]-indexof G in the literature. The case m = n, that is a covering with perfectmatchings, is known to be strictly related to an outstanding conjectureof Berge and Fulkerson. In this paper we study in some details the casem = n-1. We show how this parameter can be large for cubic graphswith low connectivity and we furnish some evidence that each cyclically4-connected cubic graph of order 2n has excessive [n-1]-index at most 4.Finally, we discuss the relation between excessive [n-1]-index and someother graph parameters such as oddness and circumference.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
