Counting triangles in graphs with no wheels of order at least five

Abstract

For a family of graphs $\mathcal{F}$, a graph $G$ is said to be $\mathcal{F}$-free if it contains no member of $\mathcal{F}$ as a subgraph. A wheel graph $W_k$ is a graph on $k+1$ vertices formed by joining a new vertex to all vertices of a $k$-cycle. Given an integer $k\ge 3$, we consider the problem of determining the maximum number of triangles in a $W_{\ge k}$-free graph, where $W_{\ge k}=\{W_{\ell }:\ell \ge k\}$. The case $k=3$ was raised by Gallai, who proposed a conjecture for this case (see Erdős [5]. Gallai's conjecture was disproved by Zhou [17] and independently by Füredi, Goemans, and Kleitman [9]. In this paper, we study the case $k=4$. Namely, for every integer $n\ge 3$, we determine the maximum number of triangles in an $n$-vertex $W_{\ge 4}$-free graph and characterize all extremal graphs.

14 pages