Sridar Kuttan Pootheri

"Characterizing and counting classes of unlabeled 2-connected graphs"

Applying the Tutte decomposition of 2-connected graphs into 3-block trees we provide unique structural characterizations of several classes of 2-connected graphs, including minimally 2-connected graphs, minimally 2-edge-connected graphs, critically 2-connected graphs, critically 2-edge-connected graphs, 3-edge-connected graphs, 2-connected cubic graphs and 3-connected cubic graphs. We also give a characterization of minimally 3-connected graphs.

Cycle index sum equations for counting unlabeled minimally 2-connected graphs, unlabeled 2-connected minimally 2-edge-connected graphs and unlabeled 2-connected 3-edge-connected graphs are derived from the structural relations. Polynomial space counting algorithms are then developed using cycle index sum inversion techniques. The appendices contain tables of the numbers of these three classes of 2-connected graphs, by number of nodes and number of edges, obtained by computer implementation of the algorithms. These are listed for node orders up to 32, 25 and 34 respectively.