Covering cubic graphs with matchings of large size
From MaRDI portal
Publication:2848743
zbMATH Open1277.05135arXiv1210.3930MaRDI QIDQ2848743FDOQ2848743
Authors: S. Bonvicini, G. Mazzuoccolo 
Publication date: 26 September 2013
Published in: The Australasian Journal of Combinatorics (Search for Journal in Brave)
Abstract: Let m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of covering the edge-set of G with the minimum number of matchings of size m. This number is called excessive [m]-index of G in literature. The case m=n, that is a covering with perfect matchings, is known to be strictly related to an outstanding conjecture of Berge and Fulkerson. In this paper we study in some details the case m=n-1. We show how this parameter can be large for cubic graphs with low connectivity and we furnish some evidence that each cyclically 4-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 some other graph parameters as oddness and circumference.
Full work available at URL: https://arxiv.org/abs/1210.3930
Recommendations
- Berge-Fulkerson conjecture on certain snarks
- A revival of the girth conjecture
- The smallest nontrivial snarks of oddness 4
- On snarks that are far from being 3-edge colorable
- Decomposition of snarks
- On disjoint matchings in cubic graphs
- The hunting of a snark with total chromatic number 5
- scientific article; zbMATH DE number 6472882
- Covering graphs with matchings of fixed size
\([m\)-matching]excessive \([m\)-index of a graph \(G\)]
Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (6)
This page was built for publication: Covering cubic graphs with matchings of large size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848743)
