TOPICS
Search

Accordion Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The accordion graph A_(n,k) is the quartic graph defined for integers n>=3 and 0<k<=n/2 by taking vertices u_i and v_i for i=1, ..., n, with subscripts interpreted modulo n, and edge set

{u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+k):i=1,...,n}.

It is therefore formed from two n-graph cycles by adding a matching between corresponding vertices and a second matching offset by k.

The special case k=1 gives the n-antiprism graph, which is isomorphic to the circulant graph Ci_(2n)(1,2). More generally, accordion graphs are closely related to quartic circulants, and Gauci and Zerafa (2022) studied their Hamiltonicity, matchings, and isomorphism with quartic circulants.

Precomputed properties for accordion graphs are implemented in the Wolfram Language as GraphData[{"Accordion", {n, k}}].

See also

Antiprism Graph, Circulant Graph, Hamiltonian Graph, Quartic Graph

Explore with Wolfram|Alpha

References

Gauci, J. B. and Zerafa, J. P. "Accordion Graphs: Hamiltonicity, Matchings and Isomorphism with Quartic Circulants." Disc. Appl. Math. 321, 126-137, 2022.House of Graphs. Accordion Graphs. (16,6)-accordion graph, (20,6)-accordion graph, and others.

Cite this as:

Weisstein, Eric W. "Accordion Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AccordionGraph.html

Subject classifications