Extremal graphs without a semi-topological wheel
Elad Aigner‐Horev · Journal of Graph Theory · 2011
For 2≤r∈ℕ, let Sr denote the class of graphs consisting of subdivisions of the wheel graph with r spokes in which the spoke edges are left undivided. Let ex(n, Sr) denote the maximum number of edges of a graph containing no Sr-subgraph, and let Ex(n, Sr) denote the set of all n-vertex graphs containing no Sr-subgraph that are of size ex(n, Sr). In this paper, a conjecture is put forth stating that for r≥3 and n≥2r + 1, ex(n, Sr) = (r − 1)n − ⌈(r − 1)(r − 3/2)⌉ and for r≥4, Ex(n, Sr) consists of a single graph which is the graph obtained from Kr − 1, n − r + 1 by adding a maximum matching to the color class of cardinality r − 1. A previous result of C. Thomassen [A minimal condition implying a special K4-subdivision, Archiv Math 25 (1974), 210–215] implies that this conjecture is true for r = 3. In this paper it is shown to hold for r = 4. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:326-339, 2011