EUVIMEDEUVIMED entdecken
Crossref

Perfect Matching Index versus Circular Flow Number of a Cubic Graph

Edita Máčajová, Martin Škoviera

SIAM Journal on Discrete Mathematics · 2021-01 · 35 (2) · 1287-1297

DOI: 10.1137/20m1359407 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 14.06.2021. Verfasst von Edita Máčajová und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 9 Literaturangaben. Gefördert von: Vedecká Grantová Agentúra MŠVVaŠ SR a SAV.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The perfect matching index of a cubic graph $G$, denoted by $\pi(G)$, is the smallest number of perfect matchings that cover all the edges of $G$. According to the Berge--Fulkerson conjecture, $\pi(G)\le5$ for every bridgeless cubic graph $G$. The class of graphs with $\pi\ge 5$ is of particular interest as many conjectures and open problems, including the famous cycle double cover conjecture, can be reduced to it. Although nontrivial examples of such graphs are very difficult to find, a few infinite families are known, all with circular flow number $\Phi_c(G)=5$. It has been therefore suggested [Abreu et al., Electron. J. Combin., 23 (2016), P3.54] that $\pi(G)\ge 5$ might imply $\Phi_c(G)\ge 5$. In this article we dispel these hopes and present a family of cyclically 4-edge-connected cubic graphs of girth at least 5 with $\pi\ge 5$ and $\Phi_c\le 4+\frac23$.

Förderung

  • Vedecká Grantová Agentúra MŠVVaŠ SR a SAV

Zitieren

APA

Máčajová, E., & Škoviera, M. (2021). Perfect Matching Index versus Circular Flow Number of a Cubic Graph. SIAM Journal on Discrete Mathematics, 35(2), 1287-1297. https://doi.org/10.1137/20m1359407

Vancouver

Máčajová E, Škoviera M. Perfect Matching Index versus Circular Flow Number of a Cubic Graph. SIAM Journal on Discrete Mathematics. 2021;35(2):1287-1297. doi:10.1137/20m1359407

BibTeX
@article{Majov2021,
  author = {Máčajová, Edita and Škoviera, Martin},
  title = {Perfect Matching Index versus Circular Flow Number of a Cubic Graph},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2021},
  volume = {35},
  number = {2},
  pages = {1287--1297},
  doi = {10.1137/20m1359407}
}
Kostenlos starten →