Non-isomorphic signatures on some generalised Petersen graph

Deepak Sehrawat, Bikash Bhattacharjya


In this paper we find the number of different signatures of P(3, 1),P(5, 1) and P(7, 1) up to switching isomorphism, where P(n, k) denotes the generalised Petersen graph, 2k < n. We also count the number of non-isomorphic signatures on P(2n + 1, 1) of size two for all n ≥ 1, and we conjecture that any signature of P(2n + 1, 1), up to switching, is of size at most n + 1.


signed graph, generalised Petersen graph, balance, switching, switching isomorphism

Full Text:




J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.

D. Cartwright and F. Harary, Structural balance: a generalization of Heiders theory, Psychol. Rev. 63 (1956), 277–293.

R. Frucht, J.E. Graver and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211–218.

F. Harary, On the notion of balance of a signed graph. Michigan Math. J. 2 (1953-54), 143–146.

R. Naserasr, E. Rollova, and E. Sopena, Homomorphisms of signed graphs, J. Graph Theory, 79 (2015), 178–212.

V. Sivaraman, Some topics concerning graphs, signed graphs and matroids, PhD Thesis, The Ohio State University, 2012.

V. Yegnanarayanan, On some aspects of the generalized Petersen graph, Electron. J. Graph Theory Appl. 5 (2) (2017), 163–178.

T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1) (1982), 47–74.

T. Zaslavsky, Six signed Petersen graphs, and their automorphisms, Discrete Math. 312 (9) (2012), 1558–1583.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats