CirculantGraph

The circulant graph on n vertices arranged in a circle, joined by one or more fixed offsets.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageCirculantGraph✓↗

CirculantGraph(n, k)vertex i joined to i +/- k (mod n), for a single offset k.

SageMathenumeratio_graph(graphs.CirculantGraph(n, k))

CirculantGraph(n, {k1, k2, …})the union of the connection sets for every offset given.

Typed signatures

Type	Package	Applies
(integer, integer | list<integer>) -> value	combinatorics	always

Domain: Collections

Details

• Each vertex has degree 2 per offset, except an offset of exactly n/2 (n even), which gives only one edge per vertex (i and i + n/2 are each other's only match at that offset).

Examples

Basic #

live ↗

In$\mathrm{VertexDegree}(\mathrm{CirculantGraph}(8, 2), 1)$Out$2$

live ↗

In$\mathrm{EdgeCount}(\mathrm{CirculantGraph}(10, \bigl\lbrack1, 3\bigr\rbrack))$Out$20$

Each vertex joins its neighbours at steps 2 and 4 around a 10-cycle

live ↗

In$\mathrm{CirculantGraph}(10, \bigl\lbrack2, 4\bigr\rbrack)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(4, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(7, 9), \mathrm{UndirectedEdge}(8, 10), \mathrm{UndirectedEdge}(9, 1), \mathrm{UndirectedEdge}(10, 2), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(5, 9), \mathrm{UndirectedEdge}(6, 10), \mathrm{UndirectedEdge}(7, 1), \mathrm{UndirectedEdge}(8, 2), \mathrm{UndirectedEdge}(9, 3), \mathrm{UndirectedEdge}(10, 4)\bigr\rbrack)$

Scope #

A single jump of 2 on 5 vertices gives a pentagram

live ↗

In$\mathrm{CirculantGraph}(5, 2)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(4, 1), \mathrm{UndirectedEdge}(5, 2)\bigr\rbrack)$

Applications #

The pentagram is symmetric, so every vertex has eccentricity 2

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{CirculantGraph}(5, 2), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{CirculantGraph}(5, 2)))$Out$\bigl\lbrack2, 2, 2, 2, 2\bigr\rbrack$

Properties #

Jumps $1,2,3$ on 6 vertices connect everything, so degree 5

live ↗

In$\mathrm{VertexDegree}(\mathrm{CirculantGraph}(6, \bigl\lbrack1, 2, 3\bigr\rbrack))$Out$\bigl\lbrack5, 5, 5, 5, 5, 5\bigr\rbrack$

Using all jumps gives $K_6$

live ↗

In$\bigl\lbrack\mathrm{CirculantGraph}(6, \bigl\lbrack1, 2, 3\bigr\rbrack), \mathrm{CompleteGraph}(6)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(6, 1), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(4, 6), \mathrm{UndirectedEdge}(5, 1), \mathrm{UndirectedEdge}(6, 2), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(3, 6)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(1, 6), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(3, 6), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(4, 6), \mathrm{UndirectedEdge}(5, 6)\bigr\rbrack)\bigr\rbrack$

A jump of 1 is the cycle graph

live ↗

In$\bigl\lbrack\mathrm{CirculantGraph}(6, 1), \mathrm{CycleGraph}(6)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(6, 1)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(6, 1)\bigr\rbrack)\bigr\rbrack$

About

Examples	8
Checked against	Wolfram Language 8 agreeSageMath 3 agree4 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: CycleGraph, HararyGraph