Skip to main content
SpringerLink
Log in

Isomorphism Checking of I-graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Boben M., Pisanski T., Žitnik A.: I-graphs and the corresponding configurations. J. Comb. Des. 13, 406–424 (2005)

    Article  MATH  Google Scholar 

  2. Bouwer I.Z., Chernoff W.W., Monson B., Star Z.: The Foster Census. Charles Babbage Research Centre, Winnipeg, Canada (1988)

    MATH  Google Scholar 

  3. Coxeter H.S.M.: Self-dual configurations and regular graphs. Bull. Am. Math. Soc. 56, 413–455 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  4. Frucht R., Graver J.E., Watkins M.E.: The groups of the generalized Petersen graphs. Proc. Camb. Phil. Soc. 70, 211–218 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  5. Horton J.D., Bouwer I.Z.: Symmetric Y-graphs and H-graphs. J. Comb. Th. (B) 53, 114–129 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  6. Horvat, B.: Unit-distance representations of graphs. Ph.D. Thesis (in Slovene), University of Ljubljana, Ljubljana, Slovenia (2009)

  7. Horvat, B., Pisanski, T.: Unit distance representations of the Petersen graph in the plane. Ars Combin. (to appear)

  8. Horvat B., Pisanski T.: Products of unit distance graphs. Discret. Math. 310, 1783–1792 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Horvat, B., Pisanski, T., Žitnik, A.: All generalized Petersen graphs are unit-distance graphs (submitted)

  10. 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)

    Article  MATH  Google Scholar 

  11. Lovrečič Saražin M., Marušič D.: Vertex-transitive expansions of (1,3)-graphs. Discret. Math. 310, 1772–1782 (2010)

    Article  MATH  Google Scholar 

  12. Nedela R., Škoviera M.: Which generalized Petersen graphs are Cayley graphs? . J. Graph Theory 19, 1–11 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  13. Petkovšek M., Zakrajšek H.: Enumeration of I-graphs: burnside does it again. Ars Math. Contemp. 2, 241–262 (2009)

    MathSciNet  MATH  Google Scholar 

  14. Petkovšek M., Pisanski T.: Counting disconnected structures: chemical trees, fullerenes, I-graphs, and others. Croat. Chem. Acta 78, 563–567 (2005)

    Google Scholar 

  15. 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)

  16. 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)

  17. Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/~njas/sequences/

  18. Steimle A., Staton W.: The isomorphism classes of the generalized Petersen graphs. Discret. Math. 309, 231–237 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Watkins M.E.: A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Comb. Theory 6, 152–164 (1969)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Primorska, Koper, Slovenia

    Boris Horvat

  2. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

    Boris Horvat, Tomaž Pisanski & Arjana Žitnik

  3. University of Ljubljana, Ljubljana, Slovenia

    Tomaž Pisanski & Arjana Žitnik

Authors
  1. Boris Horvat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomaž Pisanski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arjana Žitnik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tomaž Pisanski.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1086-2

Keywords

Mathematics Subject Classification (2000)

Search

Navigation