On r ‐Connected Graphs with No Semi‐topological r ‐Wheel

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 K r , 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 subclassH 0 of ante‐contraction members of H plays a key role. Second, the members ofH 0 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) mapsH 0 onto the class of trees whose internal vertices have even degrees, equal to 6 for any vertex adjacent to a leaf. The description ofH 0 (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 ( 2 r − 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 − 1 2.