Small Cubics

Here are the first few Small Order Simple Connected Cubic Hamiltonian Graphs. Each vertex is connected to three others - two of them neighbours on the outer Hamiltonian circuit as the circumference of the 2n-gon, and one more 'across the circuit'. Such graphs (i.e. cubic graphs with Hamiltonian circuits) can be described in text with the help of a system from Lederberg, Coxeter and Frucht, aka LCF notation.

It's not until we have 10 vertices that there is enough 'room' for symmetry breaking to turn up. The usual (on this site) blue and pink colourings obtain for symmetric and non-symmetric graphs, respectively.

1 4 Vertex

Graph 0 1 2 3
LCF code [2]4

2 6 Vertex

Graph 0 1 2 3 4 5
LCF code [3]6[3,-2,2]2

7 8 Vertex

Graph 0 1 2 3 4 5 6 7
LCF code [4]8[4,-3,3,4]2 [4,-2,4,2]2[2,-3,-2,2,3,-2,3,-3]
Graph  
LCF code [4,-2,3,3,4,-3,-3,2] [3,-3]4 [2,2,-2,-2]2  

29 10 Vertex

Graph 0 1 2 3 4 5 6 7 8 9
LCF code [5,−4,4,5,5]2 [−3,4,−3,3,4;–] [4,−3,4,4,−4;–] [−4,3,5,5,−3,4,4,5,5,−4]
Graph  
LCF code [5]10 [-3,3]5 [5,5,-3,5,3]2  
Graph  
LCF code [5,3,5,−4,−3,5,2,5,−2,4] [−4,2,5,−2,4,4,4,5,−4,−4] [−3,2,4,−2,4,4,−4,3,−4,−4]  
Graph
LCF code [2,3,−2,5,−3]2 [3,−2,4,−3,4,2,−4,−2,−4,2] [2,3,−2,3,−3;–] [−4,4,2,5,−2]2  
Graph
LCF code [2,5,−2,5,5]2 [2,4,−2,3,4;–] [5,−4,4,−4,4]2 [5,−4,−3,3,4,5,−3,4,−4,3]
Graph  
LCF code [−4,3,3,5,−3,−3,4,2,5,−2] [3,−4,−3,−3,2,3,−2,4,−3,3] [3,−3,5,−3,2,4,−2,5,3,−4]  
Graph
LCF code [4,2,3,−2,−4,−3,2,2,−2,−2] [2,−3,−2,2,2;–] [−2,−2,3,3,3;–] [2,2,−2,−2,5]2
Graph
LCF code [2,−4,−2,5,2,4,−2,4,5,−4] [5,−2,2,4,−2,5,2,−4,−2,2] [5,−3,−3,3,3]2 [−4,4,−3,5,3]2

No comments:

Post a Comment