TOPICS
Search

Alternating Group Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
AlternatingGroupGraph

The alternating group graph AG_n is the undirected Cayley graph of the set of 2(n-2) generators of the alternating group A_n given by g_3^-, g_3^+, g_4^-, g_4^+, ..., g_n^-, and g_n^+, where

g_i^-=(1,i,2)
(1)
g_i^+=(1,2,i)
(2)

in permutation cycle notation (Jwo et al. 1993).

AG_n is a special case of the arrangement graph A_(n,k) given by A_(n,n-2). This and other special cases are summarized in the following table and illustrated above.

ngraph
2singleton graph K_1
3triangle graph C_3
4cuboctahedral graph
narrangement graph A_(n,n-2)

AG_n is Hamiltonian (Jwo et al. 1993), and when n>=3 is an integer, AG_n contains 2n-4 mutually independent (directed) Hamiltonian cycles (Su et al. 2012).

The independence ratios for A_n with n=2, 3, 4, 5, and 6 are 1, 1/3, 1/3, 1/3, and 1/3, but the value for A_7 is apparently not known (S. Wagon, pers. comm., Jul. 30, 2018).

Precomputed properties of alternating group graphs are available in the Wolfram Language as GraphData[{"AlternatingGroupGraph", n}].

See also

Alternating Group, Arrangement Graph, Cayley Graph, Permutation Star Graph

Explore with Wolfram|Alpha

References

Jwo, J. S.; Lakshmivarahan, S.; and Dhall, S. K. "A New Class of Interconnectional Networks Based on the Alternating Group." Networks 23, 315-326, 1993.Su, H.; Chen, S.-Y.; and Kao, S.-S. "Mutually Independent Hamiltonian Cycles in Alternating Group Graphs." J. Supercomput. 61, 560-571, 2012.

Referenced on Wolfram|Alpha

Alternating Group Graph

Cite this as:

Weisstein, Eric W. "Alternating Group Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AlternatingGroupGraph.html

Subject classifications