2025/03/14 by Ning Song, Song, Ning, Jinze Hu +5 · 2 citations
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2503.11473
openalex publication_date 2025/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a fixed graph H, a graph G is called H-saturated if G does not contain H as a (not necessarily induced) subgraph, but G+e contains a copy of H for any e∈ E(G). The saturation number of H, denoted by \rm sat(n,H), is the minimum number of edges in an n-vertex H-saturated graph. A wheel Wn is a graph obtained from a cycle of length n by adding a new vertex and joining it to every vertex of the cycle. A well-known result of Erdős, Hajnal and Moon shows that \rm sat(n,W3)=2n-3 for all n≥ 4 and K2\vee Kn-2 is the unique extremal graph, where \vee denotes the graph join operation. In this paper, we study the saturation number of W4. We prove that \rm sat(n,W4)=\lfloor(5n-10)/(2)\rfloor for all n≥ 6 and give a complete characterization of the extremal graphs.