zbMATH — the first resource for mathematics

Inversion of cycle index sum relations for 2- and 3-connected graphs. (English) Zbl 0728.05026
Algebraic inversion of cycle index sum relations is employed to derive new algorithms for counting unlabeled graphs which are (a) 2-connected, (b) 2-connected and homeomorphically irreducible, and (c) 3-connected. The new algorithms are significantly more efficient than earlier ones, both asymptotically and for modest values of the order. Time- and space- complexity analyses of the algorithms are provided. Tables of computed results are included for the number n of nodes satisfying \(n\leq 26\) in case (a) and \(n\leq 25\) in cases (b) and (c). These are totals over all values of the number of q of edges. Reference is made to a technical report available from the authors which includes tables of the values for each q when \(n\leq 16\) in case (a) and \(n\leq 18\) in cases (b) and (c).
Reviewer: R.W.Robinson

05C30 Enumeration in graph theory
05C40 Connectivity
Full Text: DOI