PROPERTIES OF CUBIC GRAPHS

The databases contained on this page seek to provide an encompassing list of important properties for exhaustive sets of cubic graphs. The objective is to allow cross-referencing of such properties to identify special cubic graphs of interest to researchers. Each set contains, for all cubic graphs of a given size, a property signature that describes the properties of that graph. The properties currently listed are:

ID number as output by GENREG [1] with the command: genreg k 3 3
Hamiltonicity (0 for non-Hamiltonian, 1 for Hamiltonian)
Number of undirected Hamiltonian cycles (0 for non-Hamiltonian graphs)
Hyperhamiltonicity (0 for non-Hyperhamiltonian, 1 for Hyperhamiltonian)
Hypohamiltonicity (0 for non-Hypohamiltonian, 1 for Hypohamiltonian)
Edge-connectivity
Cyclic edge-connectivity
Girth
Planarity (0 for non-planar, 1 for planar)
Bipartiteness (0 for non-bipartite, 1 for bipartite)
Snark (0 for non-Snark, 1 for Snark)
Filar the graph is located in (number of triangles)
Gene (0 for descendant, 1 for gene)
Mutant (0 for non-mutant, 1 for mutant)
Number of ancestor genes (1 if graph is a gene)
Size of largest ancestor gene (the size of the graph for a gene)
Second-largest eigenvalue
Diameter

Currently the datbases are available for all cubic graphs up to 20 vertices. They can be downloaded individually as text files, or as a combined Excel file.

  • 4-vertex cubic graphs
  • 6-vertex cubic graphs
  • 8-vertex cubic graphs
  • 10-vertex cubic graphs
  • 12-vertex cubic graphs
  • 14-vertex cubic graphs
  • 16-vertex cubic graphs
  • 18-vertex cubic graphs
  • 20-vertex cubic graphs
  • Combined Excel file
  • Download all files

EXAMPLE

A 10-vertex graph with the following property signature:

4 1 4 0 0 2 2 3 1 0 0 5 0 0 3 4 2.41421 3

  • Has ID #4 as output by GENREG with the command: genreg 10 3 3
  • Is Hamiltonian
  • Contains 4 undirected Hamiltonian cycles
  • Is non-Hyperhamiltonian
  • Is non-Hypohamiltonian
  • Is 2-edge-connected
  • Is 2-cyclic-edge-connected
  • Has girth 3
  • Is planar
  • Is non-bipartite
  • Is not a Snark
  • Is in the 5th filar
  • Is not a Gene
  • is not a mutant
  • Contains 3 ancestor genes
  • Has a largest ancestor gene of size 4
  • Has second-largest eigenvalue of 2.41421
  • Has diameter 3

If you believe there are additional properties we should be including in the property signature, please contact Michael Haythorpe.

[1]  M. Meringer: Fast Generation of Regular Graphs and Construction of Cages.Journal of Graph Theory 30, 137-146, 1999.

© Flinders Hamiltonian Cycle Project