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