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"


Basic operations and properties for graphs

On the automorphism group of the Petersen graph

  • The Petersen graph is available as follows:
    is_isomorphic(petersen_graph(), g2mg(kneser_g(5,2)));
  • 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)));
    gap> Size(AutGroupGraph(JohnsonGraph(40,2)));
    gap> Factorial(40);
  • 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}));
  • 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.