Redirigiendo al acceso original de articulo en 24 segundos...
Inicio  /  Algorithms  /  Vol: 14 Par: 1 (2021)  /  Artículo
ARTÍCULO
TITULO

Constructing Minimally 3-Connected Graphs

João Paulo Costalonga    
Robert J. Kingan and Sandra R. Kingan    

Resumen

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 ??-1 n - 1 vertices and ??-2 m - 2 edges, ??-1 n - 1 vertices and ??-3 m - 3 edges, and ??-2 n - 2 vertices and ??-3 m - 3 edges.

 Artículos similares