No Detail Found!

A note on isomorphic generalized Petersen graphs with an application to the crossing number of GP [3k 1; k] and GP [3k + 1; k]

Author(s)
John Baptist Gauci Department of Mathematics, University of Malta,Msida,Malta
Cheryl Zerafa Xuereb Department of Mathematics, Junior College,Msida,Malta
Abstract
For positive integers n and k, the generalized Petersen graph GP [n; k] is the graph on the 2n vertices fu0; u1; : : : ; un 1; x0; x1; : : : ; xn 1g and the edges ffui; xig; fui; ui+1g; fxi; xi+kgg, where i = 0; 1; : : : ; n 1, addition modulo n. The crossing number of a graph G is defined as the least number of crossings of edges of G when G is drawn in a surface, which in our case will be the Euclidean plane. We prove a conjecture presented by Zhou and Wang [Int. J. Math. Comb. 4 (2012) 116-123] on the crossing number of GP [3k 1; k] and derive a quick way to check if a result by Watkins can be used to establish whether two generalized Petersen graphs on different parameters are isomorphic.
Publication Details
Page(s) 44-46
DOI DOI not available
Published Journal: Discrete Mathematics Letters, Volume: 2, Issue: 0, Year: 2019

Request the full text from PASTIC

Keywords
generalized Petersen graph, Drawing, crossing number
References
Clancy K.,Haythorpe M.,Newcombe A. . .A survey of graphs with known or bounded crossing numbers. arXiv:1901.05155v3 [math.CO]., : .
Coxeter H. S. M. .1950 .Self-dual configurations and regular graphs. Bull. Amer. Math. Soc, 56 : 413-455.
Exoo G.,Harary F.,J. Kabell, F. .1981 .The crossing numbers of some generalized Petersen graphs. , 48 : 184-188.
Fiorini S. .1986 .On the crossing number of generalized Petersen graphs. , 30 : 225-241.
Guy R. K. .1969 .The decline and fall of Zarankiewicz's Theorem. Proof Techniques in Graph Theory, : 63-69.
Richter R .B.,G. Salazar, R .B. .2002 .The crossing number of P (N; 3. , 18(2) : 381-394.
Tura P. .1977 .´ n, A note of welcome. J. Graph Theory, 1 : 7-9.
Watkins M. .1969 .A theorem on Tait colourings with an application to the generalized Petersen graphs. J. Combin. Theory Ser. B, 6 : 152-164.
Xiaohui L.,Yuansheng Y.,Wenping Z.,Lei S.,L. Weiming, S. .2009 .The crossing numbers of some generalized Petersen graphs with small order. , 157 : 1016-1023.
Zarankiewicz K. .1954 .On a problem of P. Tur a´n concerning graphs, Fund. , 41 : 137-145.
Zhou Z.,J. Wang, Z. .2012 .The crossing number of the generalized Petersen graph P [3k 1; k]. Int. J. Math. Comb. 4, : 116-123.
0

Citations

0

Downloads

14

Views