Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T01:14:33.108Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphical Regular Representations of Non-Abelian Groups, I

Published online by Cambridge University Press:  20 November 2018

Lewis A. Nowitz  and
Mark E. Watkins
Lewis A. Nowitz
Affiliation:
American Electric Power Service Corporation, 2 Broadway, New York, New York
Mark E. Watkins
Affiliation:
Syracuse University, Syracuse, New York
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, all groups and graphs considered are finite and all graphs are simple (in the sense of Tutte [8, p. 50]). If X is such a graph with vertex set V(X) and automorphism group A(X), we say that X is a graphical regular representation (GRR) of a given abstract group G if

(I) G ≅ A(X) , and

(II) A(X) acts on V(X) as a regular permutation group; that is, given u, v ∈ V(X), there exists a unique φ ∈ A(X) for which φ(u) = v.

That for any abstract group G there exists a graph X satisfying (I) is well-known (cf. [3]).

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 24 , Issue 6 , December 1972 , pp. 993 - 1008
Copyright
Copyright © Canadian Mathematical Society 1972

References

1. Chong-Yun, Chao, On a theorem of Sabidussi, Proc. Amer. Math. Soc. 15 (1964), 291–292.Google Scholar
2. Coxeter, H. S. M. and Moser, W. O. J., Generators and relations for discrete groups (Springer-Verlag, Berlin, 1957).Google Scholar
3. Roberto, Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938), 239–250.Google Scholar
4. Wilfried, Imrich, Graphs with transitive Abelian automorphism group in Combinatorial Theory and Its Applications, Proceedings of the Combinatorial Conference at Balatonfüred, Hungary, 1969.Google Scholar
5. Lewis A., Nowitz, On the non-existence of graphs with transitive generalized dicyclic groups, J. Combinatorial Theory 4 (1968), 49–51.Google Scholar
6. Gert, Sabidussi, On a class of fixed-point free graphs, Proc. Amer. Math. Soc. 9 (1958), 800–804.Google Scholar
7. Gert, Sabidussi, On vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438.Google Scholar
8. Tutte, W. T., Connectivity in graphs (University of Toronto Press, Toronto, 1966).Google Scholar
9. Mark E., Watkins, On the action of non-abelian groups on graphs, J. Combinatorial Theory 11 (1971), 95–104.Google Scholar
10. Mark E., Watkins and Lewis A., Nowitz, On graphical regular representations of direct products of groups, Monatsh. Math. 76 (1972), 168–171.Google Scholar