63.66 An example

We conclude this chapter with a simple example to illustrate further the use of GRAPE.

In this example we construct the Petersen graph P, and its edge graph (often called line graph) EP. We compute the (global) parameters of EP, and so verify that EP is distance-regular (see BCN89). We also show that there is just one orbit of 1-factors of P under the automorphism group of P (but you should read the documentation of the function CompleteSubgraphsOfGivenSize to see exactly what that function does).

    gap> P := Graph( SymmetricGroup(5), [[1,2]], OnSets,
    >          function(x,y) return Intersection(x,y)=[]; end );
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 2)( 6, 8)( 7, 9), ( 1, 3)( 4, 8)( 5, 9),
        ( 2, 4)( 3, 6)( 9,10), ( 2, 5)( 3, 7)( 8,10) ),
      schreierVector := [ -1, 1, 2, 3, 4, 3, 4, 2, 2, 4 ],
      adjacencies := [ [ 8, 9, 10 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 2, 5 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
          [ 1, 3 ], [ 1, 4 ], [ 3, 5 ], [ 4, 5 ], [ 3, 4 ] ] )
    gap> Diameter(P);
    2
    gap> Girth(P);
    5
    gap> EP := EdgeGraph(P);
    rec(
      isGraph := true,
      order := 15,
      group := Group( ( 1, 4)( 2, 5)( 3, 6)(10,11)(12,13)(14,15), ( 1, 7)
        ( 2, 8)( 3, 9)(10,15)(11,13)(12,14), ( 2, 3)( 4, 7)( 5,10)( 6,11)
        ( 8,12)( 9,14), ( 1, 3)( 4,12)( 5, 8)( 6,13)( 7,10)( 9,15) ),
      schreierVector := [ -1, 3, 4, 1, 3, 1, 2, 3, 2, 4, 1, 4, 1, 2, 2 ],
      adjacencies := [ [ 2, 3, 13, 15 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], [ 3, 5 ] ], [ [ 1, 2 ], [ 4, 5 ] ],
          [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 5 ] ],
          [ [ 1, 4 ], [ 2, 5 ] ], [ [ 2, 5 ], [ 3, 4 ] ],
          [ [ 1, 5 ], [ 2, 3 ] ], [ [ 1, 5 ], [ 2, 4 ] ],
          [ [ 1, 5 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ],
          [ [ 2, 3 ], [ 4, 5 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
          [ [ 2, 4 ], [ 3, 5 ] ], [ [ 1, 3 ], [ 4, 5 ] ],
          [ [ 1, 4 ], [ 3, 5 ] ] ] )
    gap> GlobalParameters(EP);
    [ [ 0, 0, 4 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> CompleteSubgraphsOfGivenSize(ComplementGraph(EP),5);
    [ [ 1, 5, 9, 11, 12 ] ] 

Previous Up Top
Index

GAP 3.4.4
April 1997