Cycle Complement Graph
CycleComplementGraph
The n-cycle complement graph C^__n is the graph complement of the cycle graph C_n. Cycle complement graphs are special cases of circulant graphs given by Ci_n(1,2,...,|_n/2_|). The first few are illustrated above in embeddings obtained by removing a cycle from the complete graph K_n (top) and in "standard" circulant graph form (bottom).
The wheel complement graph W^__(n+1) is isomorphic to the graph disjoint union C^__n union K_1 of the cycle complement graph C^__n and singleton graph.
Special cases are summarized in the table below.
n graph name
3 empty graph K^__3
4 ladder rung graph 2P_2
5 cycle graph C_5
6 prism graph P_2 square C_3
7 circulant graph Ci_7(1,2)
8 circulant graph Ci_8(1,2,4)
9 circulant graph Ci_9(1,2,3)
10 circulant graph Ci_(10)(1,2,4,5)
See also
Cycle Graph, Graph Complement, Path Complement Graph, Wheel Complement GraphExplore with Wolfram|Alpha
WolframAlpha
Cite this as:
Weisstein, Eric W. "Cycle Complement Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CycleComplementGraph.html