ON THE WALKS ON CAYLEY GRAPHS
Abstract
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
graphs.
Keywords
Full Text:
PDFReferences
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
Refbacks
- There are currently no refbacks.
ISSN 0352-9665 (Print)