Premium
On ( 2 , k ) ‐connected graphs
Author(s) -
Durand de Gevigney Olivier,
Szigeti Zoltán
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22433
Subject(s) - combinatorics , mathematics , vertex (graph theory) , connectivity , discrete mathematics , conjecture , strongly connected component , 1 planar graph , graph , chordal graph
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.