Matthias Kriesell: Degree sequences and edge connectivity
Vir: Seminar za teorijo grafov in algoritme
For each positive integer k, we give a finite list C(k) of Bondy--Chvátal type conditions to a nondecreasing sequence d=(d_1,...,d_n) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected.
We prove that C(k) is and must be large by showing that it contains p(k) many pairwise logically irredundant conditions, where p(k) is the number of partititons of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, as, for example, essentially k-edge-connectivity.
Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to k=3, this verifies a recent conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for k=2 we obtain an alternative prove for their result on bridgeless connected graphs. The explicit list for k=4 is given, too.