Decomposition of generalized Petersen graphs into claws, cycles and paths

M. Subbulakshmi, I. Valliammal

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 {u0,u1,u2,...,un−1, v0, v1, v2,..., vn−1} and edge-set consisting of all edges of the form uiui+1,uivi and vivi+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 S3 if n is even and P4 and (n−1) copies of S3 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 Cn/2 and n/2 copies of P2 if n is even and Cn, P4,  [n/2]  copies of S3 and (n/2 −1) copies of P2 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 S3 and d copies of P4. GP(n,3), n ≥ 8 can be decomposed into n copies of S3 if n is even and P6, P2 and (n−2) copies of S3 if n is odd.

Full Text: PDF

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.

J. Math. Comput. Sci.

ISSN: 1927-5307

Editorial Office: jmcs@scik.org

 

Copyright ©2021 JMCS