Decomposition of generalized Petersen graphs into claws, cycles and paths

Abstract

Let G = (V,E) be a finite graph with n vertices. Let n and k be positive integers where n ≥ 3 and 1 ≤ k < n/2. The Generalized Petersen Graph GP(n,k) is a graph with vertex set {u₀,u₁,u₂,...,u_n−1, v₀, v₁, v₂,..., v_n−1} and edge-set consisting of all edges of the form u_iu_i+1,uivi and v_iv_i+k where 0 ≤ i ≤ n−1, the subscripts being reduced modulo n. Obviously GP(n, k) is always a cubic graph and GP(5,2) is the well-known Petersen graph. In this paper, we show that GP(n,1), n ≥ 3 can be decomposed into n copies of S₃ if n is even and P₄ and (n−1) copies of S₃ if n is odd. Also, we show that GP(n,2), n ≥ 5 can be decomposed into n/2 copies of S3, 2 copies of C_n/2 and n/2 copies of P₂ if n is even and C_n, P₄,  [n/2]  copies of S₃ and (n/2 −1) copies of P₂ if n is odd. GP(n,2), n ≥ 5 and n = 3d, d = 2,3,... can be decomposed into 2d copies of S3 and d copies of P4. GP(n,2), n ≥ 5 and n = 4d, d = 2,3,... can be decomposed into 3d copies of S₃ and d copies of P₄. GP(n,3), n ≥ 8 can be decomposed into n copies of S₃ if n is even and P₆, P₂ and (n−2) copies of S₃ if n is odd.