Extremal graphs without a semi‐topological wheel

For 2≤ r ∈ℕ, let S r 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, S r ) denote the maximum number of edges of a graph containing no S r ‐subgraph, and let Ex ( n, S r ) denote the set of all n ‐vertex graphs containing no S r ‐subgraph that are of size ex ( n, S r ). In this paper, a conjecture is put forth stating that for r ≥3 and n ≥2 r + 1, ex ( n, S r ) = ( r − 1) n − ⌈( r − 1)( r − 3/2)⌉ and for r ≥4, Ex ( n, S r ) consists of a single graph which is the graph obtained from K r − 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 K 4 ‐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