TY - JOUR
T1 - Extremal graphs without a semi-topological wheel
AU - Horev, Elad
PY - 2011/12
Y1 - 2011/12
N2 - For 2≤r εN, 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.
AB - For 2≤r εN, 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.
KW - Semi-topological minors
KW - Subdivisions of the wheel graph
UR - http://www.scopus.com/inward/record.url?scp=84857361809&partnerID=8YFLogxK
U2 - 10.1002/jgt.20562
DO - 10.1002/jgt.20562
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:84857361809
SN - 0364-9024
VL - 68
SP - 326
EP - 339
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 4
ER -