Constructing minimally 3-connected graphs

MaRDI QIDQ6356697zbMATH OpenFDO

Authors João Paulo Costalonga, Robert J. Kingan, S. R. Kingan

Publication date 22 December 2020

Has companion code repository https://github.com/rkingan/m3c

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A $3$-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. In order to test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G^{\prime }$ from the cycles of $G$, where $G^{\prime }$ is obtained from $G$ by one of the two operations above. We eliminate isomorphs using certificates generated by McKay's isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with $n$ vertices and $m$ edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges.

This page was built for publication: Constructing minimally 3-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356697)