On the Maximum Number of Triangles in Wheel-Free Graphs

Summary

Gallai raised the question of determining t(n), the maximum number of triangles in graphs of n vertices with acyclic neighborhoods. Here we disprove his conjecture (t(n) ∼ n²/8) by exhibiting graphs having n²/7.5 triangles. We improve the upper bound of (n² − n)/6 to t(n) ≤ n²/7.02 + O(n). For regular graphs, we further decrease this bound to n²/7.75 + O(n).

Introduction

Let WFG_n be the class of graphs on n vertices with the property that the neighborhood of any vertex is acyclic. A graph G is given by its vertex set V(G) and edge set E(G). The subgraph induced by X ⊂ V(G) is denoted by G[X]. The neighborhood N(v) of vertex v is the set of vertices adjacent to v. Note that v ∉ N(v). The degree of v ∈ V(G), denoted by d_v or d_v(G), is the size of the neighborhood: d_v = |N(v)|. The maximum (minimum) degree is denoted by Δ (δ), or Δ(G) (δ(G), respectively) to avoid misunderstandings. A matching M ⊂ E(G) is a set of pairwise disjoint edges. A wheel W_i is obtained from a cycle C_i by adding a new vertex and edges joining it to all the vertices of the cycle; the new edges are called the spokes of the wheel (i ≥ 3, W₃ = K₄). Therefore, WFG_n consists of all graphs on n vertices containing no wheel.