Premium
Extremal graphs without a semi‐topological wheel
Author(s) -
Horev Elad
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20562
Subject(s) - combinatorics , mathematics , conjecture , graph , vertex (graph theory) , discrete mathematics , induced subgraph , cardinality (data modeling) , computer science , data mining
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