Is the Franklin graph a Cayley graph?

franklin graph

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!

Advertisements
This entry was posted in Math and tagged , , , . Bookmark the permalink.

One Response to Is the Franklin graph a Cayley graph?

  1. Alain Jacques says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s