科研速览 · Science Skim继续刷下去 · Keep skimming →
◆ Journal of Graph Theory2026-03-19· Mathematics

A Strong Structural Stability of C2k+1‐Free Graphs

Zilong Yan, Yuejian Peng

原始摘要(英文原文)· Original abstract
ABSTRACT Füredi and Gunderson showed that is achieved only on if . It is natural to study how far a ‐free graph is from being bipartite. If a graph and a graph have at most one vertex in common and there is no edge connecting and , then we call graph a suspension to graph with suspension point. Let be obtained by adding a suspension with 1 suspension point to . Let and . Ren, Wang, Wang, and Yang showed that if is an ‐vertex ‐free graph with , then and , and equalities hold if and only if for and . In this paper, we show that for integers with and , if is a ‐free ‐vertex graph with , then is obtained by adding suspensions to a ‘nearly balanced complete’ bipartite graph one by one and the number of vertices not in is no more than . Furthermore, the total number of vertices not in equals if and only if . Roughly speaking, we give a strong structural information for ‐free graph rather than the distance from being bipartite when if . In the proof, we introduce a new concept strong‐‐core which is the key that we can give a stronger structural stability result but a simpler proof.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

A Strong Structural Stability of C2k+1‐Free Graphs — 科研速览 Science Skim