09.05.2011 10:00 Seminarska soba v Galebu

Lecturer: dr. Ted Dobson ( Mississippi State University, Department of Mathematics and Statistics )

 

Title: The isomorphism classes of all generalized petersen graphs

Abstract:The generalized Petersen graphs GP(n, k) were introduced by Watkins in 1969, and since then have been studied extensively. For an ordered pair (n, k), where 1 ≤ k ≤ n − 1, k = n/2, the generalized Petersen graph GP(n, k) has vertex set Z₂ ×Z_n and edge set {(1, i)(1, i+1), (0, ki)(0, ki+ k), (0, i)(1, i) : i ∈ Z_n}. Many well-known graphs are generalized Petersen graphs, with GP(5, 2) being the Petersen graph itself, GP(4, 1) being the skeleton of the three dimensional cube, GP(10, 2) being the skeleton of the dodecahedron, and GP(10, 3) is the Desargues graph (the Levi or incidence graph of the Desargues configuration). In this talk, we determine necessary and sufficient conditions for two generalized Petersen graphs GP(n, k) and GP(n, ℓ) to be isomorphic. The conditions are that either k ≡ ±ℓ (mod n) or that kℓ ≡ ±1 (mod n).