Cubic Graphs With Edges in Exactly One Perfect Matching
Journal of Graph Theory · 2026-07 · 112 (3) · 276-289
DOI: 10.1002/jgt.70024 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 30.03.2026. Verfasst von Jan Goedgebeur und 4 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: Fonds Wetenschappelijk Onderzoek, Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
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 .
Förderung
- Fonds Wetenschappelijk Onderzoek
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Goedgebeur, J., Mattiolo, D., Mazzuoccolo, G., Renders, J., & Wolf, I. H. (2026). Cubic Graphs With Edges in Exactly One Perfect Matching. Journal of Graph Theory, 112(3), 276-289. https://doi.org/10.1002/jgt.70024
Vancouver
Goedgebeur J, Mattiolo D, Mazzuoccolo G, Renders J, Wolf IH. Cubic Graphs With Edges in Exactly One Perfect Matching. Journal of Graph Theory. 2026;112(3):276-289. doi:10.1002/jgt.70024
BibTeX
@article{Goedgebeur2026,
author = {Goedgebeur, Jan and Mattiolo, Davide and Mazzuoccolo, Giuseppe and Renders, Jarne and Wolf, Isaak H.},
title = {Cubic Graphs With Edges in Exactly One Perfect Matching},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {3},
pages = {276--289},
doi = {10.1002/jgt.70024}
}
EUVIMED