Enumeration of hamiltonian paths in Cayley diagrams |
| |
Authors: | David Housman |
| |
Institution: | (1) Center for Applied Mathematics, Cornell University, 14853 Ithaca, NY, U.S.A. |
| |
Abstract: | LetG be a group generated by a subset of elementsS. The Cayley diagram ofG givenS is the labeled directed graph with vertices identified with the elements ofG and (v, u) is an edge labeledh ifh S anduh=v. The sequence of elements ofS corresponding to the edges transversed in a hamiltonian path (whose initial vertex is the identity) is called a group generating sequence (abbreviatedggs) inS.In this paper a minimal upper bound for the number ofggs's in a pair of generator elements for any two-generated group is given. For all groups of the formG= a, b:b
n
=1,a
m
=b
r
,ba=ab
–1 wherem is even, it is shown that the number ofggs's in {a, b} is 1+m(n–1)/2. An algorithm is developed that yields the number ofggs's for two-generated groupsG= a, b for which ba
–1![rang](/content/p22k81863335760j/xxlarge9002.gif) G. Explicit forms for the countedggs's are also provided. |
| |
Keywords: | Primary 05C25 Secondary 05C30 |
本文献已被 SpringerLink 等数据库收录! |
|