Fact-checked by Grok 2 weeks ago

Circulant graph

In graph theory, a circulant graph is an undirected graph with vertex set \{0, 1, \dots, n-1\} for some positive integer n, where two distinct vertices i and j are adjacent if and only if their difference i - j \pmod{n} belongs to a fixed subset S \subseteq \{1, 2, \dots, n-1\} that is closed under taking additive inverses (i.e., S = -S) and does not contain 0.^[1] These graphs are a special case of Cayley graphs on the cyclic group \mathbb{Z}_n with symmetric connection set S, and they admit a cyclic automorphism of order n that cyclically permutes the vertices.^[1] Circulant graphs are vertex-transitive and regular of degree |S|, meaning every vertex has the same degree and the graph's structure is invariant under cyclic shifts.^[2] Connected circulant graphs (except the path on two vertices) are biconnected, Hamiltonian, and vertex-transitive, with their automorphism groups often containing the cyclic group as a regular subgroup and potentially larger wreath product structures depending on n and S.^[2]^[1] The spectra of circulant graphs are particularly well-studied, as their eigenvalues can be explicitly computed using roots of unity, facilitating analysis of connectivity, expansion properties, and isospectrality.^[3] Notable examples include the cycle graph C_n, obtained when S = \{1, n-1\}, and the complete graph K_n, when S = \{1, 2, \dots, n-1\}.^[2] Paley graphs, which are strongly regular graphs constructed from finite fields of prime power order congruent to 1 modulo 4, are circulant when the order is prime and serve as important examples in extremal graph theory.^[4] Other classes encompass prism graphs, Möbius ladders, and certain conference graphs, highlighting their role in enumerating symmetric structures.^[2] Circulant graphs find applications in coding theory for constructing error-correcting codes with good spectral properties, in VLSI design for efficient chip layouts exploiting symmetry, and in communication networks for modeling topologies with cyclic redundancies.^[5] They also appear in graph signal processing for shift-invariant filtering on cyclic structures and in chemistry for studying molecular energies via graph spectra.^[6]^[7]

Definition and Fundamentals

Definition

A circulant graph is an undirected graph G with vertex set V(G) = \{0, 1, \dots, n-1\}, which forms the cyclic group \mathbb{Z}_n under addition modulo n, for some positive integer n \geq 3. Two distinct vertices i and j are adjacent if and only if j - i \pmod{n} \in S, where S is the connection set, a nonempty subset of \{1, 2, \dots, \lfloor n/2 \rfloor \} with the full symmetric connection set being S \cup \{n - s \pmod{n} \mid s \in S \} \setminus \{0\}; S does not contain 0 (to avoid loops). If n is even and n/2 \in S, the elements +n/2 and -n/2 coincide, resulting in a single connection to the antipodal vertex.^[2] The standard notation for such a graph is C_n(S), where n denotes the order (number of vertices) and S specifies the (reduced) connections. This construction ensures that the graph is regular of degree $2|S| if n/2 \notin S, or $2|S| - 1 if n is even and n/2 \in S, as each vertex connects to two distinct neighbors per element in S except for the antipodal case. Circulant graphs are inherently vertex-transitive, arising from the action of the cyclic group \mathbb{Z}_n on the vertices.^[8] The adjacency matrix A of C_n(S) is a circulant matrix, meaning it is symmetric with zeros on the main diagonal and each row is a right cyclic shift of the previous row. Specifically, the entry A_{i,j} = 1 if |i - j| \pmod{n} \in S or n - |i - j| \pmod{n} \in S, and $0 otherwise; the first row thus encodes the connection set as a binary vector with 1s in positions corresponding to elements of S and their symmetric counterparts. This matrix structure facilitates eigenvalue computations using roots of unity.^[9] The concept of circulant graphs was introduced by Gert Sabidussi in 1958 as a class of fixed-point-free, vertex-transitive graphs constructed via group actions, and it was later formalized in the modern notation and properties by researchers such as Ranković and Tošić in their study of graphs with circulant adjacency matrices.^[10]^[9]

Equivalent Characterizations

A circulant graph of order n with connection set S is equivalently defined as the Cayley graph \operatorname{Cay}(\mathbb{Z}_n, S), where \mathbb{Z}_n is the cyclic group of order n under addition modulo n, and S \subseteq \mathbb{Z}_n \setminus \{0\} is symmetric (i.e., closed under negation modulo n) to ensure the graph is undirected.^[11] This equivalence holds because the vertices can be labeled by elements of \mathbb{Z}_n, with edges connecting g to g + s \mod n for each s \in S, and the group action provides the cyclic symmetry.^[3] Another equivalent characterization is that a graph is circulant if and only if its adjacency matrix is a circulant matrix, meaning each row is a right cyclic shift of the previous row, resulting in a symmetric Toeplitz structure adapted to cyclic boundaries.^[12] For a circulant graph on n vertices, the adjacency matrix A satisfies A = \operatorname{circ}(c_0, c_1, \dots, c_{n-1}), where c_0 = 0, c_i = 1 if i \in S, and the matrix commutes with the permutation matrix representing the cycle shift.^[12] Circulant graphs are also precisely the connected vertex-transitive graphs whose automorphism group contains a cyclic subgroup of order n that acts regularly on the vertices.^[11] This regular action means the subgroup is isomorphic to \mathbb{Z}_n and transitive, with each non-identity element fixing no vertices, ensuring the graph's symmetries align with cyclic permutations. Equivalently, a connected undirected graph on n vertices is circulant if its automorphism group includes a cyclic permutation of order n that cycles all vertices, generating the regular action characteristic of the cyclic group structure.^[1]^[11] This permutation serves as a generator for the rotational symmetry inherent to circulant graphs.

Basic Properties

Circulant graphs, being Cayley graphs on the additive cyclic group \mathbb{Z}_n, are vertex-transitive; that is, their automorphism group acts transitively on the vertex set, allowing any vertex to be mapped to any other by some automorphism. This property follows directly from the group action defining the graph, where left multiplication by group elements permutes the vertices regularly.^[14] As Cayley graphs, circulant graphs are also regular, with each vertex having degree equal to the cardinality of the connection set S, assuming S is symmetric (i.e., closed under negation modulo n) and excludes 0 to avoid loops in the undirected case. The regularity stems from the uniform neighborhood structure imposed by the generating set S, where the neighbors of any vertex v are precisely v + s \pmod{n} for s \in S.^[15] A key connectivity property of the circulant graph C_n(S) is that it is connected if and only if \gcd(n, S) = 1, where \gcd(n, S) denotes the greatest common divisor of n and all elements of S.^[16] If \gcd(n, S) = d > 1, the graph decomposes into d isomorphic connected components, each a circulant graph on n/d vertices.^[17] This criterion arises because the generated subgroup of \mathbb{Z}_n by S has index equal to \gcd(n, S).^[16] The automorphism group of C_n(S) always includes the cyclic group of order n as a regular subgroup, corresponding to the left translations by elements of \mathbb{Z}_n.^[18] In general, the full automorphism group is larger, often the normalizer of this cyclic subgroup within the symmetric group on n vertices, which includes reflections and other symmetries unless S generates \mathbb{Z}_n in a minimal way that preserves no additional structure.^[1] For simple cases, such as the cycle graph C_n = C_n(\{1\}), the diameter is \lfloor n/2 \rfloor and the girth is n. The diameter, meanwhile, is the maximum over all vertices of the shortest path length, often computable as the covering radius of S in \mathbb{Z}_n.^[19]

Examples and Constructions

Standard Examples

The cycle graph C_n, which consists of n vertices connected in a single cycle, is the simplest connected circulant graph and can be expressed as C_n(\{1\}), where each vertex is adjacent to the vertices at distances \pm 1 modulo n. This construction highlights the basic rotational symmetry inherent in circulant graphs, with the connection set generating the entire cycle structure.^[20]^[21] The complete graph K_n is another fundamental example, realized as the circulant graph C_n(\{1, 2, \dots, \lfloor n/2 \rfloor\}), connecting each vertex to all others except itself via the maximal symmetric connection set within the cyclic group \mathbb{Z}_n. This representation underscores how circulant graphs can achieve full connectivity while preserving vertex-transitivity.^[22]^[23] In contrast, the Petersen graph, a well-known cubic (3-regular) graph on 10 vertices, serves as a prominent non-circulant example; despite its vertex-transitivity and symmetry, it lacks the cyclic structure required for a circulant representation, distinguishing it from circulant cubic graphs such as the utility graph or prism graphs that do admit such formulations.^[24] Möbius ladders, for even orders n = 2k, are circulant graphs C_n(\{1, k\}), obtained by adding edges between opposite vertices in the cycle graph C_n, resulting in a twisted ladder topology that embeds the non-orientable Möbius strip in graph form. These graphs are 3-regular and bipartite precisely when k is odd, illustrating the interplay between parity conditions and structural properties in circulants.^[25]^[26]

Notable Families

One prominent family of circulant graphs is the Paley graphs. For a prime p \equiv 1 \pmod{4}, the Paley graph of order p is defined as the circulant graph C_p(Q), where Q is the set of nonzero quadratic residues modulo p. This construction yields a strongly regular graph with parameters (p, (p-1)/2, (p-5)/4, (p-1)/4), making it symmetric and self-complementary. Paley graphs exhibit high symmetry and have been instrumental in extremal graph theory due to their optimal clique and independence numbers relative to their order.^[27]^[27] Cubic circulant graphs form another significant parameterized family, consisting of 3-regular circulant graphs on even order n = 2m with m \geq 2. These graphs are generated as C_{2m}(\{a, m\}) for an integer a with $1 \leq a < m and \gcd(a, m) = 1 to ensure connectivity, where the connection set includes a, -a \equiv 2m - a \pmod{2m}, and the diameter edge m. A canonical example within this family is the prism graph (or circular ladder), obtained when a = 1, which is C_{2m}(\{1, m\}) and represents the Cartesian product of a cycle C_m with K_2. Variations for different a (analogous to k in \{1, k, n/2\}) produce distinct cubic structures with applications in network design, where the choice of a influences properties like Hamiltonicity and edge-transitivity.^[28]^[28]^[28] Rook's graphs also yield circulant structures under specific conditions. The rook's graph R(m,n), defined as the Cartesian product K_m \Box K_n representing rook moves on an m \times n chessboard, is circulant of order mn precisely when m and n are coprime. In this case, the cyclic symmetry arises from the combined action of the complete graph automorphisms, enabling a circulant embedding that preserves the degree m + n - 2. This family highlights how tensor-like products can produce circulants with combinatorial significance in placement problems.^[29]^[29] Complete bipartite graphs K_{m,m} appear as circulants in restricted cases tied to powers of two, though explicit constructions are less parameterized. For instance, small instances like K_{2,2} \cong C_4 are inherently circulant, and higher powers relate to hypercube projections, but general m = 2^k does not universally yield circulants without additional structure.^[30] Post-2020 research has spotlighted integral circulant graphs—those with integer eigenvalues—as a family tailored for quantum spin networks. These graphs model systems enabling perfect state transfer, where the adjacency matrix eigenvalues satisfy specific ratio conditions for quantum information propagation. A key advancement characterizes integral circulants of maximal diameter, providing constructions like path-like circulants on orders up to 20 that support this phenomenon without fractional spectra. Such families extend classical circulants algebraically, emphasizing spectra for physical applications.^[31]^[32]

Structural Properties

Self-Complementary Circulant Graphs

A circulant graph G = C_n(S) is self-complementary if it is isomorphic to its complement \overline{G}, meaning there exists a bijection between vertices that preserves adjacency and non-adjacency. In the context of circulant graphs, such an isomorphism often takes the form of a mapping i \mapsto a i + b \pmod{n}, where a is a multiplier coprime to n and b is a translation, leveraging the cyclic symmetry.^[33] Prominent examples include the cycle graph C_5, which is the circulant C_5(\{1,4\}) and isomorphic to its complement via a suitable multiplier. Paley graphs of prime order p \equiv 1 \pmod{4} provide another family, constructed as C_p(Q) where Q is the set of quadratic residues modulo p; these are self-complementary and appear as a notable family of circulant graphs.^[33] A necessary condition for the existence of any self-complementary graph is that the order n \equiv 0 or $1 \pmod{4}, as the number of edges must be n(n-1)/4. For circulant graphs, which are regular of degree |S|, self-complementarity requires the degree to be (n-1)/2, implying n must be odd and thus n \equiv 1 \pmod{4}. In the case of prime order n = p, self-complementary circulant graphs exist if and only if p \equiv 1 \pmod{4}, with the Paley graph serving as the canonical example.^[33]^[34] Sachs conjectured that self-complementary circulant graphs of order n exist if and only if every prime factor of n is congruent to $1 \pmod{4}. This conjecture was proven in 1996 by Fronček, Rosa, and Širáň, establishing both the necessity and sufficiency of the condition on prime factors. An alternative algebraic proof was given by Morris in 2004.^[33]^[34]

Connectivity and Spanning Trees

The connectivity of a circulant graph C_n(S) is determined by the greatest common divisor d = \gcd(n, S), where S = \{s_1, \dots, s_k\} is the connection set with $1 \leq s_i < n/2. The graph consists of exactly d connected components, each isomorphic to the circulant graph C_{n/d}(S/d). These components correspond to the cosets of the subgroup \langle d \rangle of the cyclic group \mathbb{Z}_n generated by the elements of S. For connected circulant graphs (where d=1), the enumeration of spanning trees has been extensively studied using the Matrix-Tree Theorem, which expresses the number t(C_n(S)) as a cofactor of the Laplacian matrix. In general, for undirected circulant graphs C_n(S) with fixed jumps, t(C_n(S)) satisfies the form t_n = n a_n^2, where the sequence a_n obeys a linear recurrence relation derived from transfer matrix methods or eigenvalue products of the Laplacian. These recurrences often relate to permanents of submatrices in the transfer formulation or determinants from the characteristic polynomial of the graph.^[35] A prominent example is the circulant graph C_n(\{1,2\}), which is the square of the cycle graph C_n. The number of spanning trees in this graph is given by t(C_n(\{1,2\})) = n F_n^2, where F_n denotes the nth Fibonacci number with F_1 = 1, F_2 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 3.^[36] This formula arises from recursive decompositions of spanning trees, counting paths and cycles that cover the vertices while avoiding certain configurations.^[37] In quartic circulant graphs (degree 4), the nullity of the adjacency matrix—defined as the dimension of its kernel—provides insight into structural properties that intersect with spanning tree analyses, particularly in the context of nut graphs, which are graphs with nullity exactly 1 and applications in quantum chemistry. For a quartic circulant C_n(\{p, q\}) with $1 \leq p < q < n/2 and \gcd(p, q, n)=1, the nullity \eta(C_n(\{p, q\})) is computed as |\Psi(n, p+q) \cup \Psi(n, q-p)|, where \Psi(x, y) is the set of xth roots of unity \zeta satisfying \zeta^y = -1.^[38] Extremal nullities for such graphs on n \geq 5 vertices achieve a minimum of 0 (for odd n) or 1 (for even n under parity conditions on p and q), with the minimum 1 case corresponding to nut graphs when \gcd(n, p+q) = \gcd(n, q-p) = 1. The maximum nullity is n/2 for even n not divisible by 8, and $3n/4 otherwise.^[38] These extremal values highlight the range of kernel dimensions in connected quartic circulants, relevant to applications in nut graphs and spectral analysis.

Conjectures and Theorems

Ádám's Conjecture

Ádám's conjecture, proposed in 1967, asserts that for a circulant graph on n vertices, the only automorphisms that preserve the natural circulant vertex labeling are the affine transformations i \mapsto a i + b \pmod{n}, where a is coprime to n and b \in \{0, 1, \dots, n-1\}. This formulation suggested that isomorphism between circulant graphs could be determined solely by checking whether their connection sets are related via such affine maps, providing a simple criterion for the isomorphism problem in this class of graphs.^[39] The conjecture was disproved in 1970 when Elspas and Turner constructed a counterexample consisting of two connection sets for circulant graphs on 16 vertices that define isomorphic graphs but are not related by any affine map, thus revealing non-affine symmetries in the automorphism group.^[9] This discovery demonstrated that the automorphism group of some circulant graphs can exceed the expected affine group size, complicating the structural analysis of these graphs. The disproof has significant implications for spectral graph theory and computational problems involving circulants, as isomorphic circulant graphs share the same eigenvalues, but the existence of non-affine isomorphisms means that the spectrum alone does not always uniquely determine the connection set up to affine equivalence, thereby impacting efficient isomorphism testing algorithms for circulant graphs.^[40] In response to the counterexamples, Toida's conjecture from 1977 restricted Ádám's claim to unit circulant graphs (where the connection set consists of elements coprime to n), and this refined version was proven true independently in 2001–2002 by Balister et al. and by Lin et al.^[41] In 1962, Horst Sachs conjectured that a circulant graph on n vertices admits a self-complementary realization if and only if every prime factor of n is congruent to 1 modulo 4.^[42] Sachs established the sufficiency of this condition by providing an explicit construction for the connection set whenever n satisfies the prime factorization requirement.^[42] This conjecture generalizes an earlier result on the existence of self-complementary circulant graphs for prime orders n = 4k + 1, which follows directly as a special case since such primes are congruent to 1 modulo 4.^[42] The necessity direction—that no self-complementary circulant exists otherwise—was proven in 1999 by Brian Alspach, Joy Morris, and V. Vilfred through exhaustive case analysis on the possible forms of n, including prime powers and products of distinct primes.^[42] While the existence condition is now fully resolved, the complete classification of all possible connection sets yielding self-complementary circulants remains open, particularly for composite orders beyond prime powers. Recent partial results have advanced this for specific cases, such as products of two distinct primes both congruent to 1 modulo 4, by enumerating non-isomorphic examples and their automorphism groups.^[43] A related development concerns structural properties of low-valency circulants. In 2022, all connected closed distance magic circulant graphs of valency 3 or 4 were classified, revealing that such labelings—where vertex labels induce constant sums over closed neighborhoods—exist only for specific generating sets that ensure the graph's connectivity.^[44]

Applications and Algorithms

Network and Coding Applications

Circulant graphs have found significant applications in network topologies, particularly for achieving low-latency communication in high-performance computing (HPC) and data center environments. Optimal circulant graphs, constructed for vertex orders from $2^5 to $2^{10}, outperform traditional torus and hypercube topologies in terms of diameter and average path length, leveraging their vertex-transitivity and cyclic symmetry to minimize communication delays.^[45] This symmetry enables efficient routing and load balancing, making circulant graphs superior for scalable interconnection networks where uniform node connectivity reduces bottlenecks in parallel processing tasks.^[45] In coding theory, circulant graphs serve as Cayley graphs over abelian groups, facilitating the construction of perfect codes that partition the vertex set such that every vertex is either in the code or adjacent to exactly one code vertex. These structures exploit the cyclic nature of circulant graphs to develop error-correcting codes with optimal covering radius, applicable in reliable data transmission over noisy channels. Recent results establish conditions for the existence of such perfect codes and total perfect codes in circulant graphs derived from finite abelian groups, enhancing their utility in combinatorial coding schemes.^[46] Quantum applications of circulant graphs include modeling spin networks for perfect state transfer, where integral circulant graphs—those with integer eigenvalues—enable the complete transfer of quantum states between vertices at specific times due to their periodic spectral properties. These graphs provide viable platforms for quantum information processing, as their adjacency matrices yield unitary evolutions that support faithful state propagation without loss.^[31] Additionally, Grover walks on quadratic unitary Cayley graphs, a subclass of circulants over finite commutative rings, exhibit periodicity and perfect state transfer, allowing quantum search algorithms to explore graph structures efficiently and periodically return to initial states.^[47] Such properties position circulant graphs as key models in quantum walks for simulating physical systems and optimizing quantum algorithms. Beyond these domains, circulant graphs contribute to bounds on Ramsey numbers, with block-circulant constructions providing improved lower bounds for book Ramsey numbers R(B_r, B_s) through symmetric edge colorings that avoid monochromatic books.^[48] Historically, they have been employed in design theory for generating balanced incomplete block designs via cyclic difference sets.^[49] Recent extensions incorporate asymptotic spectrum distances to analyze graph limits in extremal combinatorics.^[50]

Algorithmic Recognition

Recognizing whether a given graph is circulant can be accomplished in polynomial time by verifying the existence of a cyclic ordering of the vertices such that the adjacency relation is preserved under cyclic shifts. This involves checking if the adjacency matrix, under an appropriate relabeling, has each row as a right cyclic shift of the previous row, which requires O(n^2) time for an n-vertex graph in the basic implementation. More advanced algorithms achieve this in linear time O(n by leveraging properties of Schur rings over cyclic groups to detect a cycle automorphism and canonical labeling.^[51] The graph isomorphism problem for circulant graphs is solvable in polynomial time, contrasting with the general case for vertex-transitive graphs, where it is GI-complete. This efficiency stems from the structured automorphism group of circulants, which is a subgroup of the wreath product of the cyclic group and the symmetric group on the connection set. Canonical labeling is obtained by considering cyclic shifts and reflections of the vertex ordering, reducing isomorphism testing to comparing these normalized forms; for graphs of prime order, this was established in O(n^4) time using association schemes.^[52]^[53] Recent algorithmic developments extend recognition techniques to specialized properties of circulant graphs, such as dispersability, where the matching book thickness equals the maximum degree. An algorithm determines dispersability for bipartite circulants and most non-bipartite circulants with small jump lengths (up to 3) by computing minimum page matching book embeddings, confirming dispersability or near-dispersability in these cases. This approach builds on the cyclic structure to embed matchings efficiently, providing explicit constructions for the embeddings.^[54]

References

[1]
[PDF] Automorphism groups of circulant graphs — a survey
Abstract. A circulant (di)graph is a (di)graph on n vertices that admits a cyclic automorphism of order n. This paper provides a survey of the work that.<|control11|><|separator|>
[2]
Circulant Graph -- from Wolfram MathWorld
A circulant graph is a graph of n graph vertices in which the i th graph vertex is adjacent to the (i+j) th and (ij) th graph vertices for each j in a list l.
[3]
[PDF] Circulant graphs and their spectra - Reed College
Figure 3: The graph Cay(Z6,{1,3}). Another definition for a circulant graph is any graph with a circulant adjacency matrix (an n × n matrix of natural ...
[4]
[PDF] arXiv:1509.05198v1 [math.CO] 17 Sep 2015
Sep 17, 2015 · The Paley graph is a circulant graph when q is prime; that is, its vertices may be labelled {0,1,...,q − 1}, and whether xy is an edge depends ...
[5]
[PDF] Further studies on circulant completion of graphs
Circulant graphs have broad spectrum of applications in the field of cloud computing, communication networks, coding theory, cellular programming, VLSI design, ...
[6]
[PDF] CIRCULANT STRUCTURES AND GRAPH SIGNAL PROCESSING - 5
Linear shift-invariant processing of graph signals rests on circulant graphs and filters. The spatial features of circulant structures also permit shift- ...
[7]
[PDF] On the energy of some circulant graphs
|λj |. This notion is related to some applications of graph theory to chemistry and has been studied intensively in the literature, see [1,3,5,6,9–12,15,17] ...
[8]
[PDF] Automorphism groups of circulant graphs — a survey - arXiv
Now that we know what automorphism groups of graphs are, we must define circulant graphs. Definition 1.4. A circulant graph X(n; S) is a Cayley graph on Zn.
[9]
[PDF] Section 1.5. Circulant Graphs
Jul 20, 2020 · A circulant graph has vertices in Zn, and edges (i,j) where (j-i) (mod n) is in C, where C is closed under additive inverses. It is a special ...
[10]
Graphs with circulant adjacency matrices - ScienceDirect.com
Abstract. Properties of a graph (directed or undirected) whose adjacency matrix is a circulant are studied. Examples are given showing that the connection set ...
[11]
ON A CLASS OF FIXED-POINT-FREE GRAPHS1
1 Written with the partial support of the National Science Foundation Grant to. Tulane University. 800. Page 2. ON A CLASS OF FIXED-POINT-FREE GRAPHS.
[12]
Integral circulant graphs - ScienceDirect.com
A graph on n vertices is called circulant if it has a circulant adjacency matrix, which is an n × n matrix commuting with the matrix Z = 0 I n - 1 1 0 .<|control11|><|separator|>
[13]
[PDF] automorphism groups and spectra of circulant graphs
Aug 29, 2016 · Cyclic groups allow us to link Cayley graphs and circulant graphs. The following results formalize this idea. Theorem 3.2. If S generates Z/nZ, ...
[14]
[PDF] CAYLEY GRAPH ENUMERATION - Simon Fraser University
Mar 3, 2000 · A circulant is a Cayley graph on a cyclic group. We denote the ... For example, since Cayley graphs are vertex transitive they are regular,.
[15]
[PDF] Algebraic Graph Theory - CMU School of Computer Science
One of the main problems of algebraic graph theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties of.
[16]
Circulants and their connectivities - Boesch - Wiley Online Library
We present a new result which answers the previously unsolved question of characterizing the connection sequence of circulants having point connectivity equal ...
[17]
[PDF] On Planarity and Colorability of Circulant Graphs⋆
... connected if and only if gcd(a1,...,am,n) = 1;. (1) more precisely, it has gcd(a1,...,am,n) isomorphic connected components. We refer to Boesch and Tindell ...
[18]
[math/0411302] Automorphism groups of circulant graphs -- a survey
Nov 13, 2004 · This paper provides a survey of the work that has been done on finding the automorphism groups of circulant (di)graphs, including the ...
[19]
Circulants and their connectivity - ResearchGate
Aug 6, 2025 · ... Since circulants belong to the family of Cayley graphs, any undirected circulant graph C n (S) is vertex-transitive and |S|-regular.
[20]
[PDF] On the diameter of integral circulant graphs 1 Introduction
It is easy to see that G is connected if and only if gcd(n, D) = 1 [7, Corollary 4.2]. Notice that G(n, S) is a Cayley graph of the additive group of Zn with.
[21]
Cohen–Macaulayness of two classes of circulant graphs
Sep 7, 2020 · There are large classes of circulant graphs. For instance, cycle graphs, complete graphs, crown graphs and Möbius ladder graphs are circulant ...
[22]
[PDF] arXiv:2409.20161v1 [math.AC] 30 Sep 2024
Sep 30, 2024 · This paper computes the regularity of powers and symbolic powers of edge ideals of cubic circulant graphs, establishing Minh's conjecture.
[23]
On the decomposition of circulant graphs using algorithmic ...
The complete graph is a circulant graph with the largest size that is known as a super-circulant graph. The size of the complete graph K m is | E ( K m ) ...
[24]
[2508.05761] The gonality of circulant graphs - arXiv
Aug 7, 2025 · The gonality of a graph measures how difficult it is to move chips around the entirety of a graph according to certain chip-firing rules without ...<|separator|>
[25]
[PDF] arXiv:math/0601758v3 [math.QA] 22 Nov 2006
Nov 22, 2006 · The techniques of the previous sections do not apply to the Petersen graph, which is not a circulant graph and cannot be written as a graph ...
[26]
[PDF] arXiv:1606.00992v3 [quant-ph] 28 Oct 2016
Oct 28, 2016 · We study two types of bipartite circulant graphs: ring graphs and directed Möbius ladder graphs. Möbius lad- der graphs can be characterized ...
[27]
Constructions for cyclic Moebius ladder systems - ScienceDirect.com
In other words, M 2 k is the circulant graph C ( 2 k , { 1 , − 1 , k } ) , namely the graph whose vertices are the elements of Z 2 k and where two vertices are ...
[28]
[PDF] Paley Graphs and Their Generalizations - arXiv
Let P be the Paley graph of order q = pn, then P is a strongly regular graph with parameters. (q,q − 1. 2. ,q − 5. 4. ,q − 1. 4. ). Proof. First, we prove that ...
[29]
[PDF] arXiv:1906.03079v1 [math.CO] 7 Jun 2019
Jun 7, 2019 · The Möbius ladder is a special case of a torus product. We note that for many circulant graphs G which are torus products, the numbers Z(G) and ...
[30]
Rook Graph -- from Wolfram MathWorld
The graph K_m square K_n has mn vertices and mn(m+n)/2-mn edges. It is regular of degree m+n-2, has diameter 3, girth 3 (for max(m,n)>=3), and chromatic
[31]
[PDF] Zero Forcing Sets and Bipartite Circulants - arXiv
Nov 26, 2010 · In this paper we introduce a class of regular bipartite graphs whose biadja- cency matrices are circulant matrices and we describe some of ...
[32]
[2307.09081] Maximal diameter of integral circulant graphs - arXiv
Jul 18, 2023 · In this paper we prove that the maximal value of the diameter of the integral circulant graph ICG_n(D) of a given order n with its prime factorization p_1^{\ ...
[33]
[PDF] Quantum state transfer on integral oriented circulant graphs - arXiv
Oct 5, 2022 · It has been discovered that integral graphs can play a role in the so-called perfect state transfer (defined below) in quantum spin networks.
[34]
[PDF] Self-complementary circulant graphs
Jan 12, 2004 · All graphs in this paper have neither loops nor multiple edges. We use V (X) and E(X) to denote the vertex set and edge set of X, ...
[35]
https://epubs.siam.org/doi/pdf/10.1137/1.9781611972962.11
[36]
[PDF] Some properties of unitary Cayley graphs
The Cayley graph X is regular of degree |S|. Its connected components are the right cosets of the subgroup generated by S. So X is connected, if S generates Γ.
[37]
https://sites.math.washington.edu/~reu/papers/2017/michael/circulant.pdf
[38]
[PDF] THE NUMBER OF SPANNING TREES IN THE SQUARE OF A ...
A classic result known as the Matrix Tree Theorem expresses the number of span- ning trees t(G) of a graph G as the value of a certain determinant.
[39]
[PDF] On Multiple methods of counting spanning trees of Circulant graphs
Aug 9, 2017 · If a spanning tree does not involve (n−1,n) then it must contain the edge (n−2,n), since the spanning tree is connected. But this is equivalent ...
[40]
On the nullities of quartic circulant graphs and their extremal null ...
Dec 25, 2022 · A circulant graph is a simple graph whose adjacency matrix can be represented in the form of a circulant matrix, while a nut graph is considered ...
[41]
On Ádám's conjecture for circulant graphs - ScienceDirect
Ádám's (1967) conjecture formulates necessary and sufficient conditions for cyclic (circulant) graphs to be isomorphic. It is known that the conjecture ...
[42]
[PDF] Constructive and analytic enumeration of circulant graphs with p
Apr 9, 2018 · The falsity of ´Adám's conjecture led to some beautiful results which characterised completely the conditions on the order of the circulant ...
[43]
Toida's Conjecture is True | The Electronic Journal of Combinatorics
Mar 31, 2002 · Let Γ Γ be a circulant graph of order n n (a Cayley graph of Zn Z n ) such that if ij∈E(Γ) i j ∈ E ( Γ ) , then i−j i − j (mod n n ) ∈S ∈ S .Missing: proven Baluster Lin
[44]
(PDF) Self-complementary circulant graphs - ResearchGate
Aug 5, 2025 · There exists a self-complementary circulant graph with n vertices if and only if every prime p in the prime factorization of n satisfies p≡1 ...
[45]
Self-Complementary Circulants of Prime-Power Order - SIAM.org
Vilfred, Self-complementary circulant graphs, Ars Combin., 53 (1999) ... Pöschel, Non-Cayley-isomorphic self-complementary circulant graphs, J. Graph ...
[46]
On closed distance magic circulants of valency up to $5$
### Summary of Main Theorem and "Closed Graph" in Context
[47]
Optimal circulant graphs as low-latency network topologies - arXiv
We obtain a series of optimal circulant topologies of size 2^5 through 2^{10} and compare them with torus and hypercube of the same sizes and ...
[48]
[2507.11871] Perfect codes in Cayley graphs of abelian groups - arXiv
Jul 16, 2025 · A perfect code in a graph is a subset where no two vertices are adjacent, and every other vertex is adjacent to exactly one in the subset.
[49]
Periodicity and perfect state transfer of Grover walks on quadratic ...
Aug 16, 2024 · This paper explores the periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs.Missing: circulants | Show results with:circulants
[50]
Lower Bounds for Book Ramsey Numbers
### Summary of Circulant Graphs in Ramsey Number Bounds
[51]
The asymptotic spectrum distance, graph limits, and the Shannon ...
Apr 25, 2024 · In this paper, building on asymptotic spectrum duality, we develop a new theory of graph distance, that we call asymptotic spectrum distance, and corresponding ...Missing: design | Show results with:design
[52]
Recognizing Circulant Graphs in Polynomial Time
May 26, 2001 · In this paper we present a time-polynomial recognition algorithm for certain classes of circulant graphs. Our approach uses coherent ...Missing: Boesch Tindell
[53]
Recognizing Circulant Graphs of Prime Order in Polynomial Time
Apr 1, 1998 · Equivalently, G G is circulant iff its vertices can be ordered such that the corresponding adjacency matrix becomes a circulant matrix. To each ...<|control11|><|separator|>
[54]
(PDF) Circulant graphs: Recognizing and isomorphism testing in ...
Aug 7, 2025 · An algorithm is constructed for recognizing the circulant graphs and finding a canonical labeling for them in polynomial time.
[55]
[2109.10163] On dispersability of some circulant graphs - arXiv
Sep 21, 2021 · A graph is dispersable if its matching book thickness equals its maximum degree. Minimum page matching book embeddings are given for bipartite and for most non ...