On r-connected graphs with no semi-topological r-wheel

Elad Horev, Michael Lomonosov

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

תקציר

A semi-topological r-wheel, denoted by Sr, is a subdivision of the r-wheel preserving the spokes. This paper describes the r-connected graphs having no Sr-subgraphs. For r>3, these are shown to be only Kr,r, while the class H of 3-connected S3-free graphs is unexpectedly rich. First, every graph G in H has an efficiently recognizable set of "contractible edges" (sometimes empty) such that a contraction minor G/F belongs to H if and only if F is a part of this set. So, the subclass H0 of ante-contraction members of H plays a key role. Second, the members of H0 have 3-edge cuts. The familiar cactus representation of minimum edge cuts (Dinits et al., in: Issledovaniya po Diskretnoy Optimizatsii, Nauka, Moscow, pp. 290-306, 1976 (Russian); also A. Schrijver, Combinatorial Optimization (Polyhedra and Efficiency), Algorithms and Combinatorics, Vol. 24, Springer, 2003, p. 253) maps H0 onto the class of trees whose internal vertices have even degrees, equal to 6 for any vertex adjacent to a leaf. The description of H0 (quite concise as expressed in appropriate terms) refers to the explicit reconstruction of the reverse image of such a tree. We also derive the upper bound (2r-3)(n-r+1) on the number of edges in an arbitrary n-vertex Sr-free graph, r≥4, and conjecture that its maximum equals (r-1)(n-r+1)+r-12.

שפה מקוריתאנגלית
עמודים (מ-עד)267-290
מספר עמודים24
כתב עתJournal of Graph Theory
כרך72
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2013
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On r-connected graphs with no semi-topological r-wheel'. יחד הם יוצרים טביעת אצבע ייחודית.

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