Generalized Johnson Graph

• A Generalized Johnson Graph denoted is defined as follows for . Let be a set of size . Then

  • The Johnson Graph is defined as

  • The Kneser Graph is the graph

• The Johnson graph is a regular graph with degree

  • In fact, it’s edge transitive.

• (Godsil 1.6.1) if , then

  • Proof: Let map from sets to their complements. This map is an isomorphism.

    Every -set has a unique complement, which is an -set.

    Also, if are -sets where then

    The converse is also true: If are -sets, then the intersection of their complements has magnitude .

• (Godsil 1.6.2) If , then the automorphism contains a subgroup isomorphic to .

  • Idea: A permutation on sets does not change the size of their intersections. That is

• (Godsil 4.1.1) is at least arc-transitive.

• (Godsil 4.1.2) is at least -transitive.

• (Godsil 4.5.1) is distance transitive.

• (Godsil 4.5.2) is distance transitive.

Petersen Graph §

• The Petersen Graph is defined as a special Johnson graph

The Petersen Graph By Leshabirukov - Own work by uploader based on http://en.wikipedia.org/wiki/File:Heawood_Graph.svg, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=5788203

• (Godsil e3.2) The Petersen graph is not a Cayley graph. In fact, it is the smallest vertex-transitive graph that is not a Cayley graph.
  • Proof: Suppose is a Cayley graph on elements isomorphic to the Petersen graph. Since must be order , Either or . In both cases, there are no -cycles, which the Petersen graph contains.
• (Godsil 4.4.1) The Petersen graph cannot be -edge colored.
• The Petersen graph is distance transitive.

Links §

• Algebraic Graph Theory by Godsil and Royle