Originators: Liqiong Xu, Xiaofeng Guo (presented by Ping Hu - REGS 2009)
Definitions: Let e be an edge in a k-connected graph G. Let G⊥e denote the graph obtained from G-e by adjusting each endpoint x of e whose degree falls to k-1 in G-e; the adjustment adds edges to turn the neighborhood of x in G-e into a clique and then deletes x. The edge e is removable if G⊥e is k-connected; otherwise, e is non-removable. For example, in the cartesian product of K3 and K2, the edges on triangles are removable, but the edges not on triangles are not. (Note: the notation in the literature uses a circled minus sign instead of ⊥, but that seems to be unavailable in html.)
Motivation: There is a long history of structural descriptions of k-connected graphs, seeking to reduce k-connected graphs to smaller k-connected graphs in order that the reverse process will give a construction procedure for all k-connected graphs. Thus here we want to characterize the k-connected graphs that have no removable edge.
Conjecture: (Xu-Guo [XG]) Let k be an integer greater than 2. If k is odd, then only k-connected graph with no removable edge is the complete graph Kk+1. If k is even, then the only such graphs are Kk+1 and the graph obtained from Kk+2 by removing a perfect matching.
Comments: The conjecture has been proved for k=3 (Barnette and Grünbaum [BG]), k=4 (Yin [Y]), and k=5 (Xu and Guo [XG]). For k≥6, Xu and Guo [XG] proved that if G is k-connected and the endpoints of any edge of G have at most k-3 common neighbors (that is, at most k-3 triangles share any edge), then G has a removable edge.
References:
[BG] D.W. Barnette and B. Grünbaum, On Steinitz's theorem concerning convex
3-polytopes and on some properties of planar graphs. Many Facets of Graph
Theory, Lecture Notes in Mathematics, Vol. 110. Springer-Verlag, New York (1966)
27-40.
[Y] J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems
Sci. Math. Sci. 19 (4) (1999) 434???438.
[XG] L. Xu and X. Guo, Removable edges in a 5-connected graph and a construction
method of 5-connected graphs, Discrete Math. 308 (9) (2008) 1726-1731