{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:55:49Z","timestamp":1765486549288,"version":"build-2065373602"},"reference-count":11,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2032 from the cycles of G, where G\u2032 is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay\u2019s 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\u22121 vertices and m\u22122 edges, n\u22121 vertices and m\u22123 edges, and n\u22122 vertices and m\u22123 edges.<\/jats:p>","DOI":"10.3390\/a14010009","type":"journal-article","created":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T22:35:48Z","timestamp":1609540548000},"page":"9","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Constructing Minimally 3-Connected Graphs"],"prefix":"10.3390","volume":"14","author":[{"given":"Jo\u00e3o Paulo","family":"Costalonga","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1tica, Universidade Federal Do Esp\u00edrito, Vit\u00f3ria 29075-910, Brazil"}]},{"given":"Robert J.","family":"Kingan","sequence":"additional","affiliation":[{"name":"Bloomberg LP, New York, NY 10165, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8232-5540","authenticated-orcid":false,"given":"Sandra R.","family":"Kingan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Brooklyn College, City University of New York, Brooklyn, NY 11210, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/S1385-7258(61)50045-5","article-title":"A theory of 3-connected graphs","volume":"23","author":"Tutte","year":"1961","journal-title":"Indag. Math."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Tutte, W.T. (1967). Connectivity in Graphs, Toronto University Press.","DOI":"10.3138\/9781487584863"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","article-title":"Dividing a graph into triconnected components","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J. Comput."},{"key":"ref_4","unstructured":"Schmidt, J.M. (2011). Structure and Constructions of 3-Connected Graphs. [Ph.D. Thesis, Free University of Berlin]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01350321","article-title":"Untersuchungen uber minimale n-fach zusammenhangende graphen","volume":"182","author":"Halin","year":"1969","journal-title":"Math. Ann."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.4153\/CMB-1963-019-5","article-title":"Some results concerning the structure of graphs","volume":"6","author":"Dirac","year":"1963","journal-title":"Can. Math. Bull."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BFb0060102","article-title":"On Steinitz\u2019s theorem concerning convex 3-polytopes and on some properties of planar graphs","volume":"110","author":"Chartrand","year":"1969","journal-title":"The Many Facets of Graph Theory. Lecture Notes in Mathematics"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0095-8956(86)90074-2","article-title":"Minimally 3-connected graphs","volume":"40","author":"Dawes","year":"1986","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00026-013-0214-5","article-title":"Strong Splitter Theorem","volume":"18-1","author":"Kingan","year":"2014","journal-title":"Ann. Comb."},{"key":"ref_10","first-page":"45","article-title":"Practical Graph Isomorphism","volume":"30","author":"McKay","year":"1981","journal-title":"Congr. Numer."},{"key":"ref_11","first-page":"69","article-title":"Generation of cubic graphs","volume":"13","author":"Brinkmann","year":"2011","journal-title":"Discret. Math. Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/9\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:06:15Z","timestamp":1760159175000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":11,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010009"],"URL":"https:\/\/doi.org\/10.3390\/a14010009","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}