OKlibrary  0.2.1.6
Chapter01.hpp File Reference

Chapter "Graphs" from [A Course in Combinatorics]. More...

Go to the source code of this file.


Detailed Description

Chapter "Graphs" from [A Course in Combinatorics].

On the notion of "graphs"

Documentation:

Basic operations and properties for graphs

On the automorphism group of the Petersen graph

  • The Petersen graph is available as follows:
    kneser_g(5,2);
      [{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}},
             {{{1,2},{3,4}},{{1,2},{3,5}},{{1,2},{4,5}},{{1,3},{2,4}},{{1,3},{2,5}},{{1,3},{4,5}},
              {{1,4},{2,3}},{{1,4},{2,5}},{{1,4},{3,5}},{{1,5},{2,3}},{{1,5},{2,4}},{{1,5},{3,4}},
              {{2,3},{4,5}},{{2,4},{3,5}},{{2,5},{3,4}}}]
    petersen_graph();
      ?GRAPH
    is_isomorphic(petersen_graph(), g2mg(kneser_g(5,2)));
      true
       
  • In the "grape"-package of GAP the Kneser-graphs are (likely incorrectly) called "JohnsonGraph"; for example
    > gap
    gap> LoadPackage("grape");
    gap> Size(AutGroupGraph(JohnsonGraph(5,2)));
    120
    gap> Size(AutGroupGraph(JohnsonGraph(40,2)));
    815915283247897734345611269596115894272000000000
    gap> Factorial(40);
    815915283247897734345611269596115894272000000000
       
  • Thus one expects the automorphism group of kneser_g(n,2) to be (naturally) isomorphic to the S_n ?!
  • Investigating closer the automorphism group of the Petersen graph:
    gap> AutGroupGraph(JohnsonGraph(5,2));
    Group([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7), (1,2)(6,8)(7,9) ])
       
    (note that GAP uses the cyle-representation of permutations).
  • The corresponding permutations in list-form are
    t1 : [1,2,4,3,5,7,6,9,8,10]$
    t2 : [1,3,2,4,6,5,7,8,10,9]$
    t3 : [1,5,6,7,2,3,4,8,9,10]$
    t4 : [2,1,3,4,5,8,9,6,7,10]$
       
    Computing the closure, we see that this should be the S_5:
    length(closure_bydef_grd(transformation_l_compo, {t1,t2,t3,t4}));
      120
       
  • We need a nice proof (so that we *see*) that the automorphism group Aut(P) of the Petersen graph is actually S_5.
    1. Via the faithful operation of S_5 we know that S_5 is a subgroup of Aut(P).
    2. Exercise 2 in Section 4.6.4 of [Handbook of computational group theory] yields an argument.

Preview on strongly regular graphs and projective plans

Exercise 1J is considered here.

Definition in file Chapter01.hpp.