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.
excessive index, Berge-Fulkerson conjecture, matching, cubic graph
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/927892
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact