×

Automorphisms of augmented cubes. (English) Zbl 1163.05024

In an earlier paper [Networks 40, 71–84 (2002; Zbl 1019.05052)], the authors defined a new family of graphs, called augmented cubes \(AQ_n\), which generalize hypercubes but have several properties that the hypercubes (and other variations) do not. The definition of \(AQ_n\) is easy: the vertex-set consists of all \(n\)-bit binary strings, and two such strings \(A = a_{1}a_{2}\ldots a_{n}\) and \(B = b_{1}b_{2}\ldots b_{n}\) are adjacent in \(AQ_n\) if and only if either \(A\) and \(B\) differ in exactly one position, or agree in the first \(k\) positions and differ in the remaining \(n-k\) positions, for some \(k \in \{0,1,\ldots,n-1\}\).
In this paper the authors prove that for all \(n \geq 4\), the automorphism group of \(AQ_n\) has order \(2^{n+3}\). They also show that \(AQ_n\) is a Cayley graph for \((\mathbb{Z}_2)^n\), although that follows from their earlier observation that \((\mathbb{Z}_2)^n\) acts transitively (and hence regularly) on the vertices of \(AQ_n\).

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

Citations:

Zbl 1019.05052
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1002/net.10033 · Zbl 1019.05052 · doi:10.1002/net.10033
[2] Choudum S. A., Distance and short parallel paths in augmented cubes · Zbl 1259.05163
[3] Chan M., The distinguishing number of the augmented cube and hypercube powers · Zbl 1154.05029
[4] Hsu, H-C., Chiang, L.C., Tan, J. M. and Hsu, L.H. International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’04. May10–122004, Hong Kong. Ring embedding in faulty augmented cubes, pp.155–161.
[5] DOI: 10.1016/j.parco.2004.10.002 · doi:10.1016/j.parco.2004.10.002
[6] DOI: 10.1023/A:1008763602097 · Zbl 1043.05061 · doi:10.1023/A:1008763602097
[7] Leighton F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992) · Zbl 0743.68007
[8] DOI: 10.1016/j.parco.2006.11.008 · doi:10.1016/j.parco.2006.11.008
[9] Sunitha V., Augmented cube: A new interconnection network (2002)
[10] DOI: 10.1016/j.ipl.2006.09.013 · Zbl 1185.05141 · doi:10.1016/j.ipl.2006.09.013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.