k-Edge-Connected Graph

A graph is -edge-connected if there does not exist a set of  edges whose removal disconnects the graph (Skiena 1990, p. 177). The maximum edge connectivity of a given graph is the smallest degree of any node, since deleting these edges disconnects the graph. Complete bipartite graphs have maximum edge connectivity.

-edge-connectedness graph checking is implemented in the Wolfram Language as KEdgeConnectedGraphQ[g, k].

The following table gives the numbers of -edge-connected graphs for -node graphs.

	OEIS	, 2, ...
0	A000719	0, 1, 2, 5, 13, 44, 191, ...
1	A052446	0, 1, 1, 3, 10, 52, 351, ...
2	A052447	0, 0, 1, 2, 8, 41, 352, ...
3	A052448	0, 0, 0, 1, 2, 15, 121, ...
4		0, 0, 0, 0, 1, 3, 25, ...
5		0, 0, 0, 0, 0, 1, 3, ...
6		0, 0, 0, 0, 0, 0, 1, ...

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 45, 1994.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Sloane, N. J. A. Sequences A000719/M1452, A052446, A052447, and A052448 in "The On-Line Encyclopedia of Integer Sequences."