EUVIMEDEUVIMED entdecken
Crossref

The saturation number of C6

Yongxin Lan, Yongtang Shi, Yiqiao Wang, Junxue Zhang

Discrete Mathematics · 2025-08 · 348 (8) · 114504

DOI: 10.1016/j.disc.2025.114504 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics, 2025-08. Verfasst von Yongxin Lan und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: China Postdoctoral Science Foundation, Fundamental Research Funds for the Central Universities, Nankai University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph $G$ is called $C_k$-saturated if $G$ is $C_k$-free but $G+e$ not for any $e\in E(\overline{G})$. The saturation number of $C_k$, denoted $sat(n,C_k)$, is the minimum number of edges in a $C_k$-saturated graph on $n$ vertices. Finding the exact values of $sat(n,C_k)$ has been one of the most intriguing open problems in extremal graph theory. In this paper, we study the saturation number of $C_6$. We prove that ${4n}/{3}-2 \le sat(n,C_6) \le {(4n+1)}/{3}$ for $n\ge9$, which significantly improves the existing lower and upper bounds for $sat(n,C_6)$.

Förderung

  • China Postdoctoral Science Foundation
  • Fundamental Research Funds for the Central Universities
  • Nankai University
  • National Natural Science Foundation of China
  • Hebei Provincial Natural Science Foundation

Zitieren

APA

Lan, Y., Shi, Y., Wang, Y., & Zhang, J. (2025). The saturation number of C6. Discrete Mathematics, 348(8), 114504. https://doi.org/10.1016/j.disc.2025.114504

Vancouver

Lan Y, Shi Y, Wang Y, Zhang J. The saturation number of C6. Discrete Mathematics. 2025;348(8):114504. doi:10.1016/j.disc.2025.114504

BibTeX
@article{Lan2025,
  author = {Lan, Yongxin and Shi, Yongtang and Wang, Yiqiao and Zhang, Junxue},
  title = {The saturation number of C6},
  journal = {Discrete Mathematics},
  year = {2025},
  volume = {348},
  number = {8},
  pages = {114504},
  doi = {10.1016/j.disc.2025.114504}
}
Kostenlos starten →