Generating connected and 2-edge connected graphs

DOI10.7155/JGAA.00187MaRDI QIDQ3184614zbMATH OpenOpenAlexFDO

Authors Ângela Mestre

Publication date 21 October 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/0710.5711

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: We focus on the algorithm underlying the main result of [A. Mestre, R. Oeckl, Generating loop graphs via Hopf algebra in quantum field theory. J. Math. Phys., 47, 122302, 2006]. This is an algebraic formula to generate all connected graphs in a recursive and efficient manner. The key feature is that each graph carries a scalar factor given by the inverse of the order of its group of automorphisms. In the present paper, we revise that algorithm on the level of graphs. Moreover, we extend the result subsequently to further classes of connected graphs, namely, (edge) biconnected, simple and loopless graphs. Our method consists of basic graph transformations only.

Recommendations

• An algebraic representation of graphs and applications to graph enumeration
• Listing All Plane Graphs
• Inversion of cycle index sum relations for 2- and 3-connected graphs
• scientific article; zbMATH DE number 3993606
• Listing All Plane Graphs

Cited in

(1)

• An algebraic representation of graphs and applications to graph enumeration

This page was built for publication: Generating connected and 2-edge connected graphs

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