Next Article in Journal
Tuning of Multivariable Model Predictive Control for Industrial Tasks
Next Article in Special Issue
Determinization and Minimization of Automata for Nested Words Revisited
Previous Article in Journal
Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game
Open AccessArticle

Constructing Minimally 3-Connected Graphs

1
Departamento de Matemática, Universidade Federal Do Espírito, Vitória 29075-910, Brazil
2
Bloomberg LP, New York, NY 10165, USA
3
Department of Mathematics, Brooklyn College, City University of New York, Brooklyn, NY 11210, USA
*
Author to whom correspondence should be addressed.
These authors contributed equally to this work.
Received: 1 December 2020 / Revised: 22 December 2020 / Accepted: 28 December 2020 / Published: 1 January 2021
(This article belongs to the Special Issue Selected Algorithmic Papers From CSR 2020)
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. 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 from the cycles of G, where G is obtained from G by one of the two operations above. We eliminate isomorphic duplicates 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 n1 vertices and m2 edges, n1 vertices and m3 edges, and n2 vertices and m3 edges. View Full-Text
Keywords: graphs; minors; minimal 3-connected graphs; cubic graphs; algorithm graphs; minors; minimal 3-connected graphs; cubic graphs; algorithm
Show Figures

Figure 1

MDPI and ACS Style

Costalonga, J.P.; Kingan, R.J.; Kingan, S.R. Constructing Minimally 3-Connected Graphs. Algorithms 2021, 14, 9. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010009

AMA Style

Costalonga JP, Kingan RJ, Kingan SR. Constructing Minimally 3-Connected Graphs. Algorithms. 2021; 14(1):9. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010009

Chicago/Turabian Style

Costalonga, João P.; Kingan, Robert J.; Kingan, Sandra R. 2021. "Constructing Minimally 3-Connected Graphs" Algorithms 14, no. 1: 9. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010009

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop