Enumeration of labelled graphs II: Cubic graphs with a given connectivity

Research output: Contribution to journalArticleResearchpeer-review


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.
Original languageEnglish
Pages (from-to)1-7
Number of pages7
JournalJournal of the London Mathematical Society
Issue number1
Publication statusPublished - 1979
Externally publishedYes

Cite this