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.

For n>=4, the accordion graph A_(n,2) has graph crossing number n. Indeed, grouping u_i with v_(i+1) identifies A_(n,2) with the circulant graph Ci_(2n)(1,n-1), whose graph crossing number was determined by Ma et al. (2005).

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.Ma, D.; Ren, H.; and Lu, J. "The Crossing Number of the Circular Graph C(2m+2,m)." Disc. Math. 304, 88-93, 2005. https://doi.org/10.1016/j.disc.2005.04.018.

Cite this as:

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

Subject classifications