### 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

_{0},u_{1},u_{2},...,u_{n−1}, v_{0}, v_{1}, v_{2},..., v_{n−1}} and edge-set consisting of all edges of the form u_{i}u_{i+1},uivi and v_{i}v_{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_{3}if n is even and P_{4}and (n−1) copies of S_{3}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_{2}if n is even and C_{n}, P_{4}, [n/2] copies of S_{3}and (n/2 −1) copies of P_{2}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_{3}and d copies of P_{4}. GP(n,3), n ≥ 8 can be decomposed into n copies of S_{3}if n is even and P_{6}, P_{2}and (n−2) copies of S_{3}if n is odd.**Published:**2021-02-04

**How to Cite this Article:**M. Subbulakshmi, I. Valliammal, Decomposition of generalized Petersen graphs into claws, cycles and paths, J. Math. Comput. Sci., 11 (2021), 1312-1322 Copyright © 2021 M. Subbulakshmi, I. Valliammal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Copyright ©2024 JMCS