7.2 Cayley graphs

Sage includes wrappers to many NetworkX commands, written mainly by Emily Kirkman and Robert Miller. The implementation of Cayley graphs was written by Bobby Moretti and Robert Miller.

sage: G = DihedralGroup(5)
sage: C = G.cayley_graph(); C
Digraph on 10 vertices

As another option to do graph theory in Sage, you may also load Leonard Soicher's GAP package GRAPE (http://www.gap-system.org/Packages/grape.html), which in turn calls the C programs in Brendan McKay's nauty (http://cs.anu.edu.au/people/bdm/nauty/). These packages require a UNIX environment to be installed (such as Linux or Cygwin - see the GRAPE readme file http://www.maths.qmul.ac.uk/~leonard/grape/READMEfile for details). To install GRAPE in Sage, see §16.8.

sage: print gap.eval('LoadPackage("grape")')   # need optional gap packages
true
sage: print gap.eval("C := CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)])")               # optional gap package
rec( isGraph := true, order := 24,
  group := Group([ (1,10,17,19)(2,9,18,20)(3,12,14,21)(4,11,13,22)(5,7,16,
        23)(6,8,15,24), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(13,15)(14,16)(17,
        18)(19,21)(20,22)(23,24) ]),
  schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2,
      1, 1, 2, 2, 1, 2 ], adjacencies := [ [ 2, 3, 7 ] ],
  representatives := [ 1 ],
  names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4),
      (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3),
      (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4),
      (1,4,2,3), (1,4)(2,3) ], isSimple := true )
sage: print gap.eval("Girth(C)")                   # optional gap package
4
sage: print gap.eval("Diameter(C)")             # optional gap package
6
sage: print gap.eval("AutGroupGraph(C)")  # optional gap package (uses nauty)
Group([ (2,7)(4,13)(5,9)(6,15)(10,19)(12,21)(16,20)(18,23),
  (1,2)(3,5)(4,6)(7,8)(9,11)(10,12)(13,19)(14,20)(15,21)(16,22)(17,23)(18,24),
  (1,3)(2,4)(5,6)(7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(19,20)(21,23)(22,24)
 ])

The command AutGroupGraph uses the 2.2 version of nauty.

Here is a more Pythonic version (thanks to Jack Schmidt for helping with this):

C3 = CyclicPermutationGroup(3)._gap_()
C = C3.CayleyGraph(C3.GeneratorsOfGroup())
V = C.Vertices().Elements()
E = C.UndirectedEdges()
L = [[y[1] for y in [x for x in E if v in x] if y[1]!=v]+[y[2]
for y in [x for x in E if v in x] if y[2]!=v] for v in V]
d = dict(zip(V,L))
G = Graph(d)
show(G.plot())

See About this document... for information on suggesting changes.