Critically (k, k)-connected graphs

AbstractThe vertex connectivity of a graph G is denoted by κ(G) and the minimum degree of G is denoted by δ(G). A finite simple graph G is said to be critically (k, k)-connected if κ(G) = κ(G) = k and for each vertex ν of G κ(G − ν) = k − 1 or κ(G − ν) = k −1, where G is the complement of G. The following result is proved: If G is acritically (k, k)-connected graphs, k ⩾ 2, δ(G) ⩾ 12(3k − 1) and δ(G) ⩾ 12(3k − 1), then |V(G)|⩽4k. Furthermore, these bounds are sharp for k ⩾ 3