Inversion of cycle index sum relations for 2- and 3-connected graphs
type: Item
instance of: scholarly article
title: Inversion of cycle index sum relations for 2- and 3-connected graphs
zbMATH Open document ID: 0728.05026
author: R. W. Robinson
author: Timothy R. S. Walsh
published in: Journal of Combinatorial Theory. Series B
publication date: 1993-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4202283
zbMATH Keywords: enumeration
zbMATH Keywords: formal power series
zbMATH Keywords: inversion
zbMATH Keywords: cycle index
zbMATH Keywords: counting
zbMATH Keywords: unlabeled graphs
MaRDI profile type: Publication
OpenAlex ID: W2000235890
DOI: 10.1006/JCTB.1993.1022
description: scientific article; zbMATH DE number 4202283