Connectivity of the graph induced by contractible edges of a k-tree

A k-tree is a Kk+1 or a graph on at least k + 2 vertices obtained from a smaller k-tree by adding one vertex and joining it to the vertices of a k-clique. Let G be a k-connected graph, and let e be an edge of G. The edge e is said to be contractible if the graph obtained from G by contracting e is again a k-connected graph, otherwise it is said to be non-contractible. Let G be a k-tree, and let G(c) = (V(G), E-C(G)), where E-C(G) denotes the set of all contractible edges of G. In this paper, we prove that kappa(G(c)) - delta(G(c)). Further, G(c) is super connected, whenever 3 <= delta(G(c)) < k. (C) 2019 Elsevier Inc. All rights reserved.