Groups with a Cayley graph isomorphic to a hypercube

DOI10.1017/S0004972700034055MaRDI QIDQ4354638zbMATH OpenOpenAlexFDO

Authors John D. Dixon

Publication date 15 January 1998

Published in Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0004972700034055

zbMATH Keywords

Cayley graphhypercube

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Generators, relations, and presentations of groups (20F05)

Review text

Let \(D_d\) be the \(d\)-dimensional hypercube. The author describes a procedure for enumerating all pairs \((G,T)\) of a group \(G\) and generating set \(T\) whose Cayley graphs are isomorphic to \(D_d\) for some \(d\). Equivalence classes of such pairs are known to correspond to conjugacy classes of regular subgroups of \(\Aut(D_d\)). The author first proves that \(\Aut(D_d)\) has a faithful representation in \(\text{Sym}(2d)\), and finds a characterization of those subgroups of \(\text{Sym}(2d)\) of order \(2^d\) which have a Cayley graph isomorphic to \(D_d\). He then uses this characterization in describing a procedure for efficiently enumerating the conjugacy classes of regular subgroups of \(\Aut(D_d)\), since equivalence classes of pairs \((G,T)\) are known to correspond to such conjugacy classes. He finishes with an explicit computation of the groups with Cayley graphs isomorphic to \(D_3\), and reports the results of computer calculations in the cases \(D_4\), \(D_5\) and \(D_6\).

Recommendations

• Enumerating Groups Acting Regularly on a d-Dimensional Cube
• On Groups with Cayley Graph Isomorphic to a Cube
• scientific article; zbMATH DE number 1543348
• Automorphisms of the cube \(n^d\)

Cites work

• Algebraic Graph Theory
• Asymmetric trees with two prescribed degrees
• Hash functions and Cayley graphs
• Isomorphism problem for Cayley graphs of \(\mathbb{Z}^ 3_ p\)
• Processor interconnection networks from Cayley graphs
• The isomorphism problem for Cayley digraphs on groups of prime-squared order

Cited in

(6)

• Arbitrary group permutations on hypercube and nonblocability of cube-connected cycles
• Automorphisms of the cube \(n^d\)
• The Smith group of the hypercube graph
• On two theorems of finite solvable groups.
• Automorphisms of the cube \(n^d\)
• On Groups with Cayley Graph Isomorphic to a Cube

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Groups with a Cayley graph isomorphic to a hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354638)