On ( 2 , k ) ‐connected graphs

A graph G is called ( 2 , k ) ‐connected if G is 2 k ‐edge‐connected and G − v is k ‐edge‐connected for every vertex v . The study of ( 2 , 2 ) ‐connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a 2 ‐vertex‐connected orientation if and only if it is (2,2)‐connected. In this paper, we provide a construction of the family of ( 2 , k ) ‐connected graphs for k even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)‐connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k ≥ 2 , what is the minimum number of edges to be added to make G ( 2 , k ) ‐connected. Both these results are based on a new splitting‐off theorem for ( 2 , k ) ‐connected graphs.