Abstract
We consider the class of I-graphs, which is a generalization of the class of the generalized Petersen graphs. We show that two I-graphs I(n, j, k) and I(n, j 1, k 1) are isomorphic if and only if there exists an integer a relatively prime to n such that either {j 1, k 1} = {a j mod n, a k mod n } or {j 1, k 1} = {a j mod n, − a k mod n }. This result has an application in the enumeration of non-isomorphic I-graphs and unit-distance representations of generalized Petersen graphs.
Similar content being viewed by others
References
Boben M., Pisanski T., Žitnik A.: I-graphs and the corresponding configurations. J. Comb. Des. 13, 406–424 (2005)
Bouwer I.Z., Chernoff W.W., Monson B., Star Z.: The Foster Census. Charles Babbage Research Centre, Winnipeg, Canada (1988)
Coxeter H.S.M.: Self-dual configurations and regular graphs. Bull. Am. Math. Soc. 56, 413–455 (1950)
Frucht R., Graver J.E., Watkins M.E.: The groups of the generalized Petersen graphs. Proc. Camb. Phil. Soc. 70, 211–218 (1971)
Horton J.D., Bouwer I.Z.: Symmetric Y-graphs and H-graphs. J. Comb. Th. (B) 53, 114–129 (1991)
Horvat, B.: Unit-distance representations of graphs. Ph.D. Thesis (in Slovene), University of Ljubljana, Ljubljana, Slovenia (2009)
Horvat, B., Pisanski, T.: Unit distance representations of the Petersen graph in the plane. Ars Combin. (to appear)
Horvat B., Pisanski T.: Products of unit distance graphs. Discret. Math. 310, 1783–1792 (2010)
Horvat, B., Pisanski, T., Žitnik, A.: All generalized Petersen graphs are unit-distance graphs (submitted)
Lovrečič Saražin M.: A note on the generalized Petersen graphs that are also Cayley graphs. J. Comb. Th. (B) 69, 226–229 (1997)
Lovrečič Saražin M., Marušič D.: Vertex-transitive expansions of (1,3)-graphs. Discret. Math. 310, 1772–1782 (2010)
Nedela R., Škoviera M.: Which generalized Petersen graphs are Cayley graphs? . J. Graph Theory 19, 1–11 (1995)
Petkovšek M., Zakrajšek H.: Enumeration of I-graphs: burnside does it again. Ars Math. Contemp. 2, 241–262 (2009)
Petkovšek M., Pisanski T.: Counting disconnected structures: chemical trees, fullerenes, I-graphs, and others. Croat. Chem. Acta 78, 563–567 (2005)
Pisanski, T., Žitnik, A.: Representing graphs and maps. In: Beineke, L.W., Wilson, R.J. (eds.) Topics in topological graph theory, Encyclopedia of mathematics and its applications, vol. 128, pp. 151–180. Cambridge University Press, New York (2009)
Pisanski, T., Randić, M.: Bridges between geometry and graph theory. In: Gorini, C.A. (ed.) Geometry at work: Papers in Applied Geometry, MAA Notes, vol. 53, pp. 174–194. Mathematical Association of America, Washington (2000)
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/~njas/sequences/
Steimle A., Staton W.: The isomorphism classes of the generalized Petersen graphs. Discret. Math. 309, 231–237 (2009)
Watkins M.E.: A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Comb. Theory 6, 152–164 (1969)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Horvat, B., Pisanski, T. & Žitnik, A. Isomorphism Checking of I-graphs. Graphs and Combinatorics 28, 823–830 (2012). https://doi.org/10.1007/s00373-011-1086-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1086-2