On Vertex-Edge-Critically n-Connected Graphs

Summary

All digraphs are determined that have the property that when any vertex and any edge that are not adjacent are deleted, the connectivity number decreases by two.

Introduction and notation

Whereas the characterization of all graphs having the property that the deletion of any two edges decreases the connectivity number by two is rather easy, and well known (see Section 2), the characterization of all graphs with the analogous property for the deletion of two vertices instead of two edges seems to be hopeless. So the following idea suggests itself. A graph or digraph G is called vertex-edge-critically n-connected (abbreviated to n-ve-critical), if the deletion of any vertex v and any edge e not incident to v decreases the connectivity number n of G by two (and such v and e exist). If we do not want to specify the connectivity number, we write vertex-edge-critical or ve-critical. When I determined the minimum number of 1-factors of a (2k)-connected graph containing a 1-factor, the ve-critical graphs played an important role and all ve-critical undirected graphs were characterized there. It was shown in that every ve-critical undirected graph is obtained in the following way. For an integer m ≥ 1, take vertex-disjoint circuits of length m + 2 and vertex-disjoint copies of (the complementary graph of the complete graph K_m on m vertices) and take all edges between these vertex-disjoint graphs.