Extremal graphs without a semi-topological wheel
✍ Scribed by Elad Horev
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 149 KB
- Volume
- 68
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
For 2 ≤ r ∈ N, 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 ≥ 2r +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.