EUVIMEDEUVIMED entdecken
Crossref

A Note on Alon–Tarsi Shortest Cycle Cover Conjecture

Yilun Luo, Rong‐Xia Hao, Rong Luo, Cun‐Quan Zhang

Journal of Graph Theory · 2026-06 · 112 (2) · 172-177

DOI: 10.1002/jgt.70026 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 20.03.2026. Verfasst von Yilun Luo und 3 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Simons Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The shortest cycle cover conjecture (SCC conjecture), proposed by Alon and Tarsi, asserts that every bridgeless cubic graph has a cycle cover with a total length at most . Tarsi further proposed a related conjecture, the conjecture, which states that every bridgeless cubic graph has a 3‐cycle cover with a total length at most . In this paper, we prove that every cyclically odd‐‐edge‐connected cubic graph has a 3‐cycle cover with a total length at most . Consequently, the SCC conjecture and the conjecture are verified in this paper for cubic graphs with cyclic odd‐edge‐connectivity at least 29 and 17, respectively. Additionally, for cubic graphs that satisfies Kaiser–Raspaud conjecture (i.e., every bridgeless cubic graph has two perfect matchings and and a parity subgraph , such that ), the SCC conjecture and the conjecture are verified for graphs with girth at least 20 and 10, respectively.

Förderung

  • National Natural Science Foundation of China
  • Simons Foundation

Zitieren

APA

Luo, Y., Hao, R., Luo, R., & Zhang, C. (2026). A Note on Alon–Tarsi Shortest Cycle Cover Conjecture. Journal of Graph Theory, 112(2), 172-177. https://doi.org/10.1002/jgt.70026

Vancouver

Luo Y, Hao R, Luo R, Zhang C. A Note on Alon–Tarsi Shortest Cycle Cover Conjecture. Journal of Graph Theory. 2026;112(2):172-177. doi:10.1002/jgt.70026

BibTeX
@article{Luo2026,
  author = {Luo, Yilun and Hao, Rong‐Xia and Luo, Rong and Zhang, Cun‐Quan},
  title = {A Note on Alon–Tarsi Shortest Cycle Cover Conjecture},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {112},
  number = {2},
  pages = {172--177},
  doi = {10.1002/jgt.70026}
}
Kostenlos starten →