Paperlane

no. 9 · Thursday 5 November 2026

The minimum number of wheel-saturating edges

Xianglei Chen and Changxiang He

math.CO · v2

Abstract

Let $G$ be an $H$-free graph. A non-edge $e$ of $G$ is called an $H$-saturating edge of $G$ if $G+e$ contains a copy of $H$. For an integer $p\geq 4$, let $W_p:=K_1\vee C_{p-1}$, and let $F_{p}:=K_1\vee P_{p-1}$. Let $f_H(n,m)$ denote the minimum number of $H$-saturating edges of an $n$-vertex $H$-free graph with exactly $m$ edges, and let $\operatorname{ex}(n,H)$ denote the Tur{á}n number. In this paper, for each fixed integer $k\geq 3$, we determine the exact value of $f_{W_{2k+1}}(n,\operatorname{ex}(n,F_{2k})+1)$ and show that $f_{W_{2k}}(n,\operatorname{ex}(n,F_{2k-1})+1)=\left(\frac{2}{33}+o(1)\right)n^2.$ Moreover, we characterize the corresponding extremal graphs.

fields
Combinatorics
pdf ↗ page arXiv:2610.33041 ↗