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 the excessive [m]-index of G in the 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 detail 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 such as oddn...
The circumference c(G) of a graph G is the length of a longest cycle. By exploit-ing our recent resu...
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U...
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and ...
Let m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of cover...
Let B be a positive integer and let G be a simple graph. An excessive [B]-factorization of G is a mi...
The excessive [m]-index of a graph G, denoted by χ′[m](G), is the minimum number of matchings of si...
We construct a family of r-graphs having a minimum 1-factor cover of cardinality 2r − 1 (disproving ...
Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as f...
The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cub...
A classic algorithm for the traveling salesman problem (TSP) on cubic graphs consists of finding a d...
AbstractFor i=2,3 and a cubic graph G let νi(G) denote the maximum number of edges that can be cover...
AbstractEvery 2-connected simple cubic graph of order n⩾6 has a cycle cover with at most ⌈n/4⌉ cycle...
It is proved that for $n \geq 6$, the number of perfect matchings in a simple connected cubic graph ...
Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matching...
Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings...
The circumference c(G) of a graph G is the length of a longest cycle. By exploit-ing our recent resu...
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U...
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and ...
Let m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of cover...
Let B be a positive integer and let G be a simple graph. An excessive [B]-factorization of G is a mi...
The excessive [m]-index of a graph G, denoted by χ′[m](G), is the minimum number of matchings of si...
We construct a family of r-graphs having a minimum 1-factor cover of cardinality 2r − 1 (disproving ...
Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as f...
The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cub...
A classic algorithm for the traveling salesman problem (TSP) on cubic graphs consists of finding a d...
AbstractFor i=2,3 and a cubic graph G let νi(G) denote the maximum number of edges that can be cover...
AbstractEvery 2-connected simple cubic graph of order n⩾6 has a cycle cover with at most ⌈n/4⌉ cycle...
It is proved that for $n \geq 6$, the number of perfect matchings in a simple connected cubic graph ...
Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matching...
Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings...
The circumference c(G) of a graph G is the length of a longest cycle. By exploit-ing our recent resu...
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U...
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and ...