Some properties of unitary addition Cayley graphs

Deepa Sinha, Pravin Garg and Anjali Singh
Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132
Volume 17, 2011, Number 3, Pages 49—59
Download full paper: PDF, 180 Kb

Details

Authors and affiliations

Deepa Sinha
Centre for Mathematical Sciences, Banasthali University
Banasthali-304022, Rajasthan, India

Pravin Garg
Centre for Mathematical Sciences, Banasthali University
Banasthali-304022, Rajasthan, India

Anjali Singh
Centre for Mathematical Sciences, Banasthali University
Banasthali-304022, Rajasthan, India

Abstract

Let Γ be an abelian group and B be a subset of Γ. The addition Cayley graph G′ = Cay+(Γ, B) is the graph having the vertex set V (G′) = Γ and the edge set E(G′) = {ab : a + bB}, where a, b ∈ Γ. For a positive integer n > 1, the unitary addition Cayley graph Gn is the graph whose vertex set is Zn, the integers modulo n and if Un denotes set of all units of the ring Zn, then two vertices a, b are adjacent if and only if a + b ∈ Un. The unitary addition Cayley graph Gn is also defined as, Gn = Cay+(Zn, Un). In this paper, we discuss the several properties of unitary addition Cayley graphs and also obtain the characterization of planarity and outerplanarity of unitary addition Cayley graphs.

Keywords

  • Cayley graph
  • Addition Cayley graph
  • Unitary Cayley graph
  • Unitary addition Cayley graph
  • Planar graph

AMS Classification

  • 05C25
  • 05C10

References

    1. R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jimenez, R. Karpman, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin., 16(1)(2009), #R117.
    2. N. Alon, Large sets in finite fields are sumsets, J. Number Theory, 126(1)(2007), 110–118.
    3. N.D. Beaudrap, On restricted unitary Cayley graphs and symplectic transformations modulo n, Electron. J. Combin., 17(2010), #R69.
    4. P. Berrizbeitia and R.E. Giudici, On cycles in the sequence of unitary Cayley graphs, Discrete Math., 282(1-3)(2004), 239–243.
    5. N. Biggs, Algebraic Graph Theory, Second Edition, Cambridge Mathematical Library, Cambridge University Press, 1993.
    6. M. Boggess, T. Jackson-Henderson, I. Jimenez, R. Karpman, The structure of unitary Cayley graphs, SUMSRI Journal, (2008).
    7. B. Cheyne, V. Gupta and C. Wheeler, Hamilton cycles in addition graphs, Rose- Hulman Undergraduate Math Journal, 4(1)(2003), 1–17.
    8. F.R.K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc., 2(2)(1989), 187– 196.
    9. I.J. Dejter and R.E. Giudici, On unitary Cayley graphs, J. Combin. Math. Combin. Comput., 18(1995), 121–124.
    10. A. Droll, A classification of Ramanujan unitary Cayley graphs, Electron. J. Combin., 17(2010), #N29.
    11. E.D. Fuchs and J. Sinz, Longest induced cycles in Cayley graphs, eprint arXiv:math/0410308v2 (2004), 1–16.
    12. E.D. Fuchs, Longest induced cycles in circulant graphs, Electron. J. Combin., 12(2005), 1–12.
    13. C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 207, 2001.
    14. B.J. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica, 25(2005), 307–326.
    15. D. Grynkiewicz, V.F. Lev and O. Serra, The connectivity of addition Cayley graphs, Electron. Notes Discrete Math., 29(2007), 135–139.
    16. D. Grynkiewicz, V.F. Lev and O. Serra, Connectivity of addition Cayley graphs, J. Combin. Theory Ser. B, 99(1)(2009), 202–217.
    17. F. Harary, Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachusetts, 1969.
    18. W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin., 14(2007), #R45.
    19. K. Kuratowski, Sur le probl_eme des courbes gauches en topologie, Fund. Math., 15(1930), 271–283.
    20. V.F. Lev, Sums and differences along Hamiltonian cycles, Electron. Notes Discrete Math., 28(2007), 25–31.
    21. V.F. Lev, Sums and differences along Hamiltonian cycles, Discrete Math., 310(3)(2010), 575–584.
    22. H.N. Ramaswamy and C.R. Veena, On the energy of unitary Cayley graphs, Electron. J. Combin., 16 (2009), #N24.
    23. H.E. Rose, A Course in Number Theory, Oxford Science Publications, Oxford University Press, 1988.
    24. T. Sander, Eigenspaces of Hamming graphs and unitary Cayley graphs, Ars Math. Contemp., 3(2010), 13–19.
    25. D.B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd. 1996.

      Related papers

      Cite this paper

      APA

      Sinha, D., Garg, P., & Singh, A. (2011). Some properties of unitary addition Cayley graphs. Notes on Number Theory and Discrete Mathematics, 17(3), 49-59.

      Chicago

      Sinha, Deepa, Pravin Garg and Anjali Singh. “Some Properties of Unitary Addition Cayley Graphs.” Notes on Number Theory and Discrete Mathematics 17, no. 3 (2011): 49-59.

      MLA

      Sinha, Deepa, Pravin Garg and Anjali Singh. “Some Properties of Unitary Addition Cayley Graphs.” Notes on Number Theory and Discrete Mathematics 17.3 (2011): 49-59. Print.

      Comments are closed.