Mathematica 9 is now available

Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Regular Graph Synthesis & Visualization
Author

Roger Beresford
Revision date

2007-11-28
Description

Regular graphs have V vertices each joined by edges to K different vertices. In cubic graphs K = 3. This notebook investigates the creation of small regular graphs with K = 3, 4, 5, 6 or 7 in the Combinatorica graph format. A procedure allows the development of regular graphs (a) as several circuits (which may be stellated) with specified edges, {b) by a generalization of the LCF (Lederburg-Coxeter-Frucht) [1] procedure, (c) as generalized Petersen-type graphs, (d) by adding new edges to a specified skeleton, or (e) as subgraphs. Hamiltonian representations (with all the vertices on a closed circuit) and near-Hamiltonian representations (a closed circuit plus a few inner vertices) can be found; these provide different "embeddings" (isomorphic visualizations) of the graphs. Many graphs have elegant structured visualizations showing symmetry.

Over 680 regular embeddings (over 540 different graphs) are supplied in RGraphData, where they are ordered by K, V, and the number of automorphisms (symmetries). Some are random examples; many are from the cited references. Isomorphs are listed together. Recognised names are included where known; all the regular graphs in the Combinatorica package are included. RGraphId[g] identifies any isomorph of graphs in the database, by comparisons of factorized characteristic polynomials. RGraphNo[ K, size, index, isomorphNo] creates the corresponding embedding for tests or display.

A few disconnected graphs and "peninsula graphs" (regular non-hamiltonian graphs with bridge edges) are included.

Procedures are supplied to validate the data, and to show a "Gallery of Graphs".

Please inform me of any errors, and provide details of any graphs or embeddings that you wish to have added to the data, at beresford22 (at) freeserve.co.uk.

[The notebook was updated by the author, November 28, 2007. Numerous graphs have been added.]
Subject

*Mathematics > Discrete Mathematics > Graph Theory
Keywords

LCF Notation, Graphs, Coxeter
Downloads Download Wolfram CDF Player

Download
RegGraph271107.nb (662.8 KB) - Mathematica Notebook [for Mathematica 5.2]