Enumeration of Labelled Graphs II: Cubic Graphs with a given Connectivity
Nicholas Wormald · Journal of the London Mathematical Society · 1979
Labelled cubic graphs and labelled connected cubic graphs were first counted by Read. In this paper, a new derivation of Read's recursive formulae for the numbers of these graphs is obtained by taking into account graphs which are cubic except for one or two points of degree 2. The same methods are then used to count labelled 2-connected cubic graphs. Labelled 3-connected cubic graphs are counted by using the partial differential equation satisfied by the exponential generating function for labelled 3-connected graphs, which was derived in the first paper in this series. As no cubic graph is 4-connected, these results determine the number of labelled k-connected cubic graphs with p points for all p and k.