Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. In fact, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. In this paper, we study the class of non-double covered cubic graphs, that is, graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass of 3-connected cubic graphs. Then, we furnish an inductive characterization of and we study properties related to the count of lonely edges. In particular, denoting by the subclass of graphs of with exactly lonely edges, we prove that is empty for , and we present a complete characterization for . The paper concludes with some insights on and .
Cubic Graphs With Edges in Exactly One Perfect Matching / Goedgebeur, J., Mattiolo, D., Mazzuoccolo, G., Renders, J., Wolf, I.H.. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 112:3(2026), pp. 276-289. [10.1002/jgt.70024]
Cubic Graphs With Edges in Exactly One Perfect Matching
Goedgebeur J.;Mazzuoccolo G.;
2026
Abstract
Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. In fact, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. In this paper, we study the class of non-double covered cubic graphs, that is, graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass of 3-connected cubic graphs. Then, we furnish an inductive characterization of and we study properties related to the count of lonely edges. In particular, denoting by the subclass of graphs of with exactly lonely edges, we prove that is empty for , and we present a complete characterization for . The paper concludes with some insights on and .
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
