Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T02:41:16.479Z Has data issue: false hasContentIssue false
  • English
  • Français

Groups with a Cayley graph isomorphic to a hypercube

Published online by Cambridge University Press:  17 April 2009

John D. Dixon
John D. Dixon
Affiliation:
Department of Mathematics and Statistics, Carleton University, Ottawa, Canada K1S 5B6
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.

A process is described for enumerating the Cayley graphs isomorphic to a binary d-cube for small values of d. There are 4 Cayley graphs isomorphic to the 3-cube, 14 isomorphic to the 4-cube, 45 isomorphic to the 5-cube and 238 isomorphic to the 6-cube. A similar method may be used for any graph with a prime power number of vertices.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 55 , Issue 3 , June 1997 , pp. 385 - 393
Copyright
Copyright © Australian Mathematical Society 1997

References

[1]Babai, L., ‘Isomorphism problem for a class of point-symmetric structures’, Acta Math. Acad. Sci. Hungar. 29 (1977), 329–336.CrossRefGoogle Scholar
[2]Biggs, N., Algebraic grapy theory (Cambridge University Press, Cambridge, 1974).CrossRefGoogle Scholar
[3]Dixon, J.D. and Mortimer, B., Permutation groups (Springer-Verlag, Berlin, Heidelberg, New York, 1996).CrossRefGoogle Scholar
[4]Dobson, E., ‘Isomorphism problem for Cayley graphs of ℤp3, Discrete Math. 147 (1995), 87–94.CrossRefGoogle Scholar
[5]Fang, X.G. and Xu, M.Y., ‘On isomorphisms of Cayley graphs of small valency’, Algebra Colloq. 1 (1994), 67–76.Google Scholar
[6]Joseph, A., ‘The isomorphism problem for Cayley digraphs on groups of prime-squared order’, Discrete Math 141 (1995), 173–183.CrossRefGoogle Scholar
[7]Kulasinghe, P. and Bettayeb, S., ‘On the multiply-twisted hypercube’, in Parallel and Distributed Computing (Montreal, PQ, 1994), Lecture Notes in Computer science 805 (Springer-Verlag, Berlin, Heidelberg, New York, 1994), pp. 267–278.Google Scholar
[8]Lubotzky, A., ‘Cayley graphs: eigenvalues, expanders and random walks’, in Surveys in Combinatorics, 1995 (Stirling), London Math. Soc. Lecture Notes 218 (Cambridge University Press, Cambridge, 1995), pp. 155–189.CrossRefGoogle Scholar
[9]McKay, B.D. and Praeger, C.E., ‘Vertex transitive graphs which are not Cayley graphs I’ J. Austral. Math. Soc. Ser. A. 56 (1994), 53–63.CrossRefGoogle Scholar
[10]Schibell, S.T. and Stafford, R.M., ‘Processor interconnection networks from Cayley graphs’, Discrete Appl. Math. 40 (1992), 333–357.CrossRefGoogle Scholar
[11]Schönert, M. et al. , GAP - Groups, Algorithms and Programming, Lehrstuhl D. für Math. (Rheinisch Westfälische Technische Hochschule, Germany, 1994).Google Scholar
[12]Zmor, G., ‘Hash functions and Cayley graphs’, Des. Codes Cryptogr. 4 (1994), 381–394.CrossRefGoogle Scholar