Majid Arezoomand

DOI Number
First page
Last page


‎Let $G$ be a group and $S$ be an inverse-closed subset of $G$ not contining of the identity element of $G$‎. ‎The Cayley graph‎

‎of $G$ with respect to $S$‎, ‎$\Cay(G,S)$‎, ‎is a graph with vertex set $G$ and edge set $\{\{g,sg\}\mid g\in G,s\in S\}$‎.

‎In this paper‎, ‎we compute the number of walks of any length between two arbitrary vertices of $\Cay(G,S)$ in terms‎

‎of complex irreducible representations of $G$‎. ‎Using our main result‎, ‎we give exact formulas for the number of walks‎

‎of any length between two vertices in complete graphs‎, ‎cycles‎, ‎complete bipartite graphs‎, ‎Hamming graphs and complete transposition‎



Cayley graph; Hamming graphs; complete transposition graphs.

Full Text:



B. Alspach and M. Dean: Honeycomb toroidal graphs are Cayley graphs, Inform. Process. Letters, 109(13) (2009) 705–708.

M. Arezoomand and B. Taeri: On the characteristic polynomial of n-Cayley

digraphs, The Electron. J. Combin., 20(3) (2013), # P57.

A. Farrugia and I. Sciriha: The main eigenvalues and number of walks in self-complementary graphs, Linear Multilinear Algebra, 62(10) (2014) 1346–1360.

W. Fulton and J. Harris, Representation theory, A first course, Graduate Texts in Mathematics 129, Springer-Verlag, New York, 1991.

G. Godsil and G. Royle: Algebraic graph theory, Springer-Verlag, New-York,

I. Gutman, C. R ücker and G. Rücker: On walks in molecular graphs, J. Chem. Inf. Comput. Sci. 41 (2001) 739–745.

M. C. Heydemann: Cayley graphs and interconnection networks, In: Hahn G.,

Sabidussi G. (eds) Graph Symmetry. NATO ASI Series (Series C: Mathematical and Physical Sciences), vol 497. Springer, Dordrecht, 1997.

R. E. Ingram: Some characters of the symmetric group, Proc. Am. Math. Soc. 1(3) (1950) 358–369.

G. James and M. Liebeck: Representations and characters of groups, Cambridge University Press, Second Edition, 2001.

R. Jajcay and J. ˇ Sirˇ an:, A construction of vertex-transitive non-Cayley graphs,

Australas. J. Combin. 10 (1994) 105–114.

R. Jajcay and J. Sirˇ an: More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121-132.

R. Jajcay, A. Malniˇ c and D. Maruˇ siˇ c: On the number of closed walks in vertex-transitive graphs, Discrete Math. 307 (2007) 484–493.

R. Kurcz: Closed walks in coset graphs and vertex-transitive non-Cayley graphs, Acta Math. Univ. Comenian. 68 (1) (1999) 127-135.

R. P. Stanley: Topic in Algebraic Combinatorics, Version of 1 February 2013.

P.-H Zieschang: Cayley graphs of finite groups, J. Algebra, 118 (1998) 447-454.

DOI: https://doi.org/10.22190/FUMI1903481A


  • There are currently no refbacks.

© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)