Extremal graphs without a semi-topological wheel

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

2 ציטוטים ‏(Scopus)

תקציר

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.

שפה מקוריתאנגלית
עמודים (מ-עד)326-339
מספר עמודים14
כתב עתJournal of Graph Theory
כרך68
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - דצמ׳ 2011
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Extremal graphs without a semi-topological wheel'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי