The saturation number of C6
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.
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}
}
EUVIMED