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
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 + b ∈ B}, where a, b ∈ Γ. For a positive integer n > 1, the unitary addition Cayley graph G_n is the graph whose vertex set is Z_n, the integers modulo n and if U_n denotes set of all units of the ring Z_n, then two vertices a, b are adjacent if and only if a + b ∈ U_n. The unitary addition Cayley graph G_n is also defined as, G_n = Cay⁺(Z_n, U_n). 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.