EUVIMEDEUVIMED entdecken
Crossref

Cubic Graphs With Edges in Exactly One Perfect Matching

Jan Goedgebeur, Davide Mattiolo, Giuseppe Mazzuoccolo, Jarne Renders, Isaak H. Wolf

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →