GAP (glabella) - Chapter 3: Examples

The Johnson graph \(J(n,k)\) is a simple graph whose vertices are the \(k\)-subsets of \(\{1,\ldots,n\}\) and two vertices are connected by an edge if and only if their intersection has size \(k-1\). If \(2k\neq n\), then the automorphism group of \(J(n,k,t)\) is isomorphic to \(S_n\) i. If \(2k=n\), then the automorphism group is isomorphic to \(C_2 \times S_n\).

gap> LoadPackage( "glabella", false );
true
gap> 
gap> ###################################
gap> v:=Combinations([1..10],5);;
gap> johnson:=List(v,x->Filtered([1..Size(v)],i->Size(Intersection(x,v[i]))=4));;
gap> bl1:=GraphCanonicalLabelling@glabella(Size(v),johnson,0,false);;
gap> Size(bl1[1]);
9
gap> bl1[3];
3445689955
gap> Print(StructureDescription(Group(bl1[1])),"\n");
C2 x S10
gap> 
gap> bl1n:=GraphCanonicalLabelling@glabella(Size(v),johnson,0,false,"densenauty");;
gap> Size(bl1n[1]);
9
gap> bl1n[3];
1564726612
gap> Print(StructureDescription(Group(bl1n[1])),"\n");
C2 x S10
gap> 
gap> SetInfoLevel( InfoGlabella, 1 );
gap> bl1sn:=GraphCanonicalLabelling@glabella(Size(v),johnson,0,false,"sparsenauty");;
#I  Invalid plain format colouring, set to 0
#I  Invalid nauty format colouring, set to [0,0]
gap> Size(bl1sn[1]);
9
gap> bl1sn[3];
771356517
gap> Print(StructureDescription(Group(bl1sn[1])),"\n");
C2 x S10

The automorphism group of the Petersen graph is isomorphic to \(S_5\). The automorphisms preserving two disjoint 5-cycles form a dihedral group of order 10.

gap> petersen:=[[2,5,6],[1,3,7],[2,4,8],[3,5,9],[1,4,10],
>     [1,8,9],[2,9,10],[3,6,10],[4,6,7],[5,7,8]];
[ [ 2, 5, 6 ], [ 1, 3, 7 ], [ 2, 4, 8 ], [ 3, 5, 9 ], [ 1, 4, 10 ], 
  [ 1, 8, 9 ], [ 2, 9, 10 ], [ 3, 6, 10 ], [ 4, 6, 7 ], [ 5, 7, 8 ] ]
gap> bl2:=GraphCanonicalLabelling@glabella(10, petersen, false, false);
#I  Invalid plain format colouring, set to 0
[ [ (4,8)(5,6)(9,10), (2,5,6)(3,4,9,7,10,8), (1,2,3,4,9,6)(5,7,8) ], 
  (1,10)(2,9)(3,6,8,4,5,7), 3430842650 ]
gap> Print(StructureDescription(Group(bl2[1])),"\n");
S5
gap> 
gap> bl2c:=GraphCanonicalLabelling@glabella(10, petersen, 
>     [1,1,1,1,1,2,2,2,2,2], false);
[ [ (2,5)(3,4)(7,10)(8,9), (1,2,3,4,5)(6,7,8,9,10) ], 
  (1,5,3,2,4)(6,10,7)(8,9), 2440551578 ]
gap> Print(StructureDescription(Group(bl2c[1])),"\n");
D10
gap> 
gap> bl2cn:=GraphCanonicalLabelling@glabella(10, petersen, 
>     [1,1,1,1,1,2,2,2,2,2], false, "densenauty");
#I  Convert colouring to nauty format
[ [ (2,5)(3,4)(7,10)(8,9), (1,2)(3,5)(6,7)(8,10) ], (3,5,4)(7,8,9), 
  1075461802 ]
gap> Print(StructureDescription(Group(bl2cn[1])),"\n");
D10
gap> 
gap> SetInfoLevel( InfoGlabella, 2 );
gap> bl2csn:=GraphCanonicalLabelling@glabella(10, petersen, 
>     [1,1,1,1,1,2,2,2,2,2], false, "sparsenauty");
#I  Convert colouring to nauty format
#I  SPARSENAUTY_GRAPH_CANONICAL_LABELING called
[ [ (2,5)(3,4)(7,10)(8,9), (1,2,3,4,5)(6,7,8,9,10) ], 
  (2,3,4,5)(6,7,10)(8,9), 1073589711 ]
gap> Print(StructureDescription(Group(bl2csn[1])),"\n");
D10

Let \(\Gamma\) be the direct product of two oriented cycles of size 3. Then \(Aut(\Gamma)\) is isomorphic to \((C_3 \times C_3).C_2\).

gap> dir_edges:=[
>     [1,2],[2,3],[3,1],[4,5],[5,6],[6,4],[7,8],[8,9],[9,7],
>     [1,4],[4,7],[7,1],[2,5],[5,8],[8,2],[3,6],[6,9],[9,3]
> ];
[ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ], [ 4, 5 ], [ 5, 6 ], [ 6, 4 ], 
  [ 7, 8 ], [ 8, 9 ], [ 9, 7 ], [ 1, 4 ], [ 4, 7 ], [ 7, 1 ], 
  [ 2, 5 ], [ 5, 8 ], [ 8, 2 ], [ 3, 6 ], [ 6, 9 ], [ 9, 3 ] ]
gap> dg:=List([1..9],i->Filtered([1..9],j->[i,j] in dir_edges));
[ [ 2, 4 ], [ 3, 5 ], [ 1, 6 ], [ 5, 7 ], [ 6, 8 ], [ 4, 9 ], 
  [ 1, 8 ], [ 2, 9 ], [ 3, 7 ] ]
gap> bl3:=GraphCanonicalLabelling@glabella(9, dg, false, true);
#I  Invalid plain format colouring, set to 0
#I  BLISS_GRAPH_CANONICAL_LABELING called
[ [ (2,4)(3,7)(6,8), (1,2,3)(4,5,6)(7,8,9) ], (1,9)(2,7,5,4,8)(3,6), 
  895877481 ]
gap> Print(StructureDescription(Group(bl3[1])),"\n");
C3 x S3
gap> 
gap> bl4:=GraphCanonicalLabelling@glabella(9, dg, false, false);
#I  Invalid plain format colouring, set to 0
#I  BLISS_GRAPH_CANONICAL_LABELING called
[ [ (2,3)(5,6)(8,9), (2,4)(3,7)(6,8), (1,2)(4,5)(7,8) ], 
  (1,9)(2,7,5,4,8)(3,6), 3628762130 ]
gap> Print(StructureDescription(Group(bl4[1])),"\n");
(S3 x S3) : C2

The last example shows that the for undirected simple graphs, one has to use symmetric list of adjacencies.

gap> path:=[[2],[3],[]];
[ [ 2 ], [ 3 ], [  ] ]
gap> GraphCanonicalLabelling@glabella(3, path, false, true);
#I  Invalid plain format colouring, set to 0
#I  BLISS_GRAPH_CANONICAL_LABELING called
[ [  ], (1,2,3), 1876527224 ]
gap> GraphCanonicalLabelling@glabella(3, path, false, false);
Error, Glabella: for undirected graphs the list of adjacencies must be symmet\
ric. at /home/nagyg/MyGAP/pkg/glabella/gap/interfaces.gi:52 called from
<function "GraphCanonicalLabelling@glabella">( <arguments> )
 called from read-eval loop at *stdin*:69
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;
gap> path_undir:=[[2],[1,3],[2]];
[ [ 2 ], [ 1, 3 ], [ 2 ] ]
gap> GraphCanonicalLabelling@glabella(3, path_undir, false, false);
#I  Invalid plain format colouring, set to 0
#I  BLISS_GRAPH_CANONICAL_LABELING called
[ [ (1,3) ], (1,2,3), 4110465937 ]

3 Examples