The Franklin graph is one of the four vertex-transitive cubic graphs on 12 vertices. From its drawing it is easy to see it is actually vertex-transitive, but I wanted to check whether it is a Cayley graph. I would use GAP together with GRAPE for that, but this time I wanted to use Sage, since it can immediately draw a graph, and I imagine that would appeal to my students.
I will use the well-known fact that a graph is a Cayley graph if and only if there is a subgroup of its automorphism group that acts regularly on the set of vertices.
First, I define the Franklin graph in LCF notation, since apparently it is not included in the graphs already defined by Sage:
sage: fr=graphs.LCFGraph(12,[5,-5],6)
I then calculate the automorphism group of the Franklin graph, considering that while the vertices of the graph are indexed from 0 to 11, in the automorphism group they are indexed from 1 to 12. So we checked that 0 is mapped to 12 and the rest are mapped to the same.
sage: aut=fr.automorphism_group(translation=True) sage: aut[1] {0: 12, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11}
The automorphism group of the graph is called gaut
, and we store in conj
a list of representatives of the conjugacy classes of its subgroups. We then check the order of such representatives:
sage: gaut=aut[0] sage: conj=gaut.conjugacy_classes_subgroups() sage: [(i,conj[i].order()) for i in range(len(conj))] [(0, 1), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 3), (7, 4), (8,4), (9, 4), (10, 4), (11, 4), (12, 4), (13, 4), (14, 4), (15, 4), (16,6), (17, 6), (18, 6), (19, 8), (20, 8), (21, 8), (22, 8), (23, 8), (24, 8), (25, 8), (26, 12), (27, 12), (28, 16), (29, 24), (30, 24), (31, 24), (32, 48)]
This says that the subgroups with index 26 and 27 have 12 elements, and so are candidates for subgroups acting regularly. We check an orbit of the 26th:
sage: conj[26].orbit(1) [1, 3, 7, 5, 9, 11]
Since the orbit does not have 12 elements, this group does not act transitively. We then check the 27th subgroup:
sage: conj[27].orbit(1) [1, 7, 3, 9, 5, 11, 12, 6, 4, 10, 2, 8] sage: len(_) 12
So this is the subgroup we were looking for, and this proves that the Franklin graph is actually a Cayley graph!
We now look for generators. For this, we name reg
the subgroup we found, and we seek to obtain the elements of reg
, sending the 0-th vertex to its neighbors.
sage: reg=conj[27] sage: fr[0] [1, 11, 5]
This means the neighbors of 0 are 1,11,5. One should probably write a function to obtain then the elements of reg
sending 0 to 1, 0 to 11 and 0 to 5. This is how I do it interactively:
sage: def f(x): return x(12)==1 ....: sage: filter(f,reg.list()) [(1,12)(2,5)(3,4)(6,7)(8,11)(9,10)] sage: a=_[0] sage: def f(x): return x(12)==11 ....: sage: filter(f,reg.list()) [(1,10)(2,9)(3,8)(4,7)(5,6)(11,12)] sage: b=_[0] sage: def f(x): return x(12)==5 ....: sage: filter(f,reg.list()) [(1,4)(2,3)(5,12)(6,11)(7,10)(8,9)] sage: c=_[0]
Finally, we construct the Cayley graph in sage, and check it is actually isomorphic to the Franklin graph. Note that we need to convert the Cayley graph to a simple graph, since Cayley graphs are directed in sage by default.
sage: cayl=reg.cayley_graph(generators=(a,b,c)).to_simple() sage: cayl.is_isomorphic(fr) True
Done!
It would be lovely to be given, explicitly, the name of the group, its elements, and the system of generators that give the Franklin graph as a Cayley graph.