Digraph3 Data set

The Franklin graph

Data type

Arc-transitive (symmetric) graph

Problematics

Kernel equation system symmetries, conjecture on kernel numbers, clustering

Description

The Franlin graph is a famous 12-vertex symmetric cubic graph discussed in map colouring. It is constructed on X = {1,2,3,4,5,6} from the circulant {-1,1} and an irregular circulant {-(3+1),1+3}.

The Franklin graph supports 17 different kernel solutions, which give three kernel orbits following the automorphisms group of the graph. The unlabelled kernel number is therefore 3.

Proof

The automorphism group is determined by three actions:

1. a lateral folding k_{-1,1} = k-1_{-(3+1),1+3} and k+1_{-1,1} = k+2_{-(3+1),1+3} with k = 2,4,6 in Z6;
2. a lateral folding (3-k)_{-1,1} = (4+k)_{-(3+1),1+3} with k = 0,1,2;
3. a rotation of degree 2: k_i = k+2_i, with k in Z6 and i = {-1,1},{-(3+1),1+3}.

When reducing the multiplicity of the kernel solutions along the orbits of the automorphic group actions, we stay in fact with only three independent kernel solutions, shown below. Solution 1 represents twelve kernel solutions, Solution 2 represents three, and Solution 3 represents two of the initial 17 kernel solutions.

Files

• The Franklin graph (Python file format)
• All 17 kernel solutions of the Franklin graph (Text file format)

References

• Weisstein, E. W., From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/FranklinGraph.html
• Godsil, Chr. and Royle, G., Algebraic Graph Theory. Springer-Verlag, 2001 [ISBN 0-387-95241-1]

Digraph3 Data Sets

All Digraph3 data sets.