Cycle graph

Cycle graphMain

Community hub

Cycle graph

8 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Cycle graph

View on Wikipedia

from Wikipedia

Cycle graph
The cycle graph $C 5$
Girth	$n$
Automorphisms	$2 n$ ( $D n$ )
Chromatic number	3 if $n$ is odd 2 otherwise
Chromatic index	3 if $n$ is odd 2 otherwise
Spectrum	$\left\{2\cos \left({\frac {2k\pi }{n}}\right);k=1,\cdots ,n\right\}$ ^[1]
Properties	2-regular Vertex-transitive Edge-transitive Unit distance Hamiltonian Eulerian Polytopal
Notation	$C n$
Table of graphs and parameters

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with $n$ vertices is called $C n$ .^[2] The number of vertices in $C n$ equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.

If $n=1$ , it is an isolated loop.

Terminology

[edit]

There are many synonyms for "cycle graph". These include simple cycle graph and cyclic graph, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, cycle, polygon, or n-gon are also often used. The term n-cycle is sometimes used in other settings.^[3]

A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle.

Properties

[edit]

A cycle graph is:

2-edge colorable, if and only if it has an even number of vertices
2-regular
2-vertex colorable, if and only if it has an even number of vertices. More generally, a graph is bipartite if and only if it has no odd cycles (Kőnig, 1936).
Connected
Eulerian
Hamiltonian
A unit distance graph

In addition:

As cycle graphs can be drawn as regular polygons, the symmetries of an n-cycle are the same as those of a regular polygon with n sides, the dihedral group of order 2n. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the n-cycle is a symmetric graph.

Similarly to the Platonic graphs, the cycle graphs form the skeletons of the dihedra. Their duals are the dipole graphs, which form the skeletons of the hosohedra.

Directed cycle graph

[edit]

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction.

In a directed graph, a set of edges which contains at least one edge (or arc) from each directed cycle is called a feedback arc set. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set.

A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.

Directed cycle graphs are Cayley graphs for cyclic groups (see e.g. Trevisan).

References

[edit]

^ Some simple graph spectra. win.tue.nl
^ Diestel (2017) p. 8, §1.3
^ "Problem 11707". Amer. Math. Monthly. 120 (5): 469–476. May 2013. doi:10.4169/amer.math.monthly.120.05.469. JSTOR 10.4169/amer.math.monthly.120.05.469. S2CID 41161918.

Sources

[edit]

Diestel, Reinhard (2017). Graph Theory (5 ed.). Springer. ISBN 978-3-662-53621-6.

External links

[edit]

Weisstein, Eric W. "Cycle Graph". MathWorld. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams)
Luca Trevisan, Characters and Expansion.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In graph theory, a cycle graph

C_n

(also known as an n-cycle) is a simple undirected graph consisting of

n

vertices connected by

n

edges to form a single closed chain, where each vertex has degree exactly 2 and

n \geq 3

.^[1]^[2] These graphs are the simplest connected 2-regular graphs and serve as fundamental building blocks for studying cyclic structures in more complex networks.^[1] Cycle graphs exhibit several key structural properties that make them central to theoretical analysis. They are uniquely Hamiltonian, meaning they possess exactly one Hamiltonian cycle (the graph itself) up to direction, and they are also edge-transitive and vertex-transitive for

n \geq 3

.^[1] The chromatic number of

C_n

is 2 if

n

is even (as even cycles are bipartite) and 3 if

n

is odd, reflecting the presence of an odd cycle that requires three colors for proper vertex coloring.^[1]^[2] The chromatic polynomial for

C_n

is given by

(k-1)^n + (-1)^n (k-1)

, where

k

is the number of available colors, which encapsulates their coloring behavior precisely.^[2] Beyond basic properties, cycle graphs play a pivotal role in broader graph theory concepts, including extremal graph theory, where they help determine the maximum number of edges in graphs avoiding specific subgraphs like short cycles.^[3] They also appear in the study of Hamiltonian and Eulerian paths, as every cycle graph is both Hamiltonian and Eulerian due to its regularity and connectivity.^[2] In applications, cycle graphs model periodic or circular phenomena, such as ring networks in computer science or molecular rings in chemistry, and their cycle spaces (vector spaces over GF(2) generated by edge sets of cycles) aid in analyzing network flows and redundancies.^[2] Special cases include the triangle graph

C_3

(complete graph

K_3

) and the square graph

C_4

, which illustrate foundational examples in connectivity and bipartitioning.^[1]

Definition and Notation

Formal Definition

In graph theory, a cycle is defined as a closed path in which no vertices are repeated except for the starting and ending vertex, which are the same.^[4] The cycle graph

C_n

(for integer

n \geq 3

) is the simple undirected graph consisting precisely of a single cycle of length

n

, with vertex set

V = \{ v_1, v_2, \dots, v_n \}

and edge set

E = \{ \{v_i, v_{i+1}\} \mid 1 \leq i \leq n-1 \} \cup \{ \{v_n, v_1\} \}

.^[1] This graph is connected and 2-regular, meaning every vertex has degree exactly 2, and it contains exactly

n

edges.^[1]

Notation and Examples

The cycle graph on

n

vertices, where

n \geq 3

, is standardly denoted by

C_n

. It consists of vertices labeled

v_1, v_2, \dots, v_n

connected by edges

\{v_i, v_{i+1}\}

for

i = 1, 2, \dots, n-1

, along with the closing edge

\{v_n, v_1\}

to form a single closed loop.^[1] This notation emphasizes the graph's circular structure, with each vertex having exactly two neighbors, reflecting its 2-regular nature.^[1] Small examples illustrate this construction clearly. The graph

C_3

is a triangle, isomorphic to the complete graph

K_3

, where all three vertices connect pairwise.^[1] The graph

C_4

resembles a square with four vertices and edges forming its perimeter, while

C_5

takes the shape of a pentagon.^[1] These polygonal forms underscore the cyclic symmetry inherent in cycle graphs, as rotating the labeling of vertices preserves the edge connections.^[1] For

C_3

, the adjacency matrix, which encodes the presence of edges between vertices, is the symmetric 3×3 matrix

\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},

011101110

, where the off-diagonal 1's indicate edges between vertices 1-2, 2-3, and 3-1, and 0's denote no self-loops.^[5] The graph $C_3$ is the smallest cycle graph and is 2-connected, meaning it remains connected after removing any single vertex.^[6]

Terminology

Key Terms

In graph theory, a cycle is a closed walk with no repeated vertices except for the initial and terminal vertices, which coincide.^[7] The girth of a graph is defined as the length of its shortest cycle; for the cycle graph

C_n

, this equals

n

.^[8] Cycle graphs form a special case of circulant graphs, in which vertices correspond to elements of the cyclic group

\mathbb{Z}_n

and edges connect each vertex solely to its immediate neighbors (jumps of

\pm 1

).^[9] All cycle graphs are 2-regular, with every vertex incident to exactly two edges.^[10]

Distinctions from Similar Graphs

A cycle graph

C_n

is distinguished from the path graph

P_n

by the addition of an edge between its two endpoints, transforming the acyclic structure of

P_n

—which is a tree with exactly two vertices of degree 1—into a closed loop that introduces cyclicity while maintaining regularity of degree 2 for all vertices.^[2] This closure ensures that

C_n

contains a Hamiltonian cycle encompassing all vertices, unlike

P_n

, where no such cycle exists due to its tree-like openness.^[2] In comparison to the complete graph

K_n

, the cycle graph

C_n

possesses the minimal number of edges (precisely

n

) required for connectivity and 2-regularity, forming a sparse structure where each vertex connects only to two neighbors, whereas

K_n

includes

\frac{n(n-1)}{2}

edges, linking every pair of distinct vertices and achieving maximum density.^[2] This sparsity in

C_n

results in a girth of

n

(the length of its shortest cycle), contrasting with the girth of 3 in

K_n

for

n \geq 3

.^[2] The wheel graph

W_n

extends the cycle graph by incorporating a central hub vertex adjacent to every vertex on the

n

-cycle rim, increasing the total vertices to

n+1

and elevating the degrees of rim vertices to 3 while the hub has degree

n

, whereas

C_n

lacks this hub and remains purely 2-regular without additional spokes.^[11] Cycle graphs are 2-vertex-connected (biconnected), with no articulation points, meaning the graph remains connected after removing any single vertex, in contrast to 1-connected trees like paths, which have vertices of degree 1 and articulation points.^[12] For

n > 3

, cycle graphs are non-chordal, as their defining induced cycle lacks any chord (an edge between non-consecutive vertices), violating the chordal graph property that every cycle of length at least 4 must contain such a chord; in contrast, chordal graphs are triangulated and free of induced cycles longer than 3.^[13]

Structural Properties

Basic Structural Features

A cycle graph

C_n

, consisting of

n

vertices connected in a single closed chain, is 2-regular, meaning every vertex has exactly degree 2.^[14] This regularity follows from each vertex being adjacent to precisely two others in the cycle.^[2] Consequently,

C_n

has exactly

n

edges, matching the number of vertices.^[15] As a connected graph with all even degrees,

C_n

is Eulerian, possessing an Eulerian circuit that traverses each edge exactly once.^[2] The diameter of

C_n

, defined as the longest shortest path between any two vertices, is

\lfloor n/2 \rfloor

.^[14] This value arises because the farthest vertices in the cycle are separated by roughly half the cycle's length.^[2] Additionally,

C_n

is Hamiltonian by definition, as the cycle itself forms a Hamiltonian cycle that visits every vertex exactly once before returning to the start.^[15] For even

n

C_n

is bipartite, with vertices partitionable into two independent sets of size

n/2

each—alternating vertices along the cycle.^[14] This bipartition is possible because even-length cycles contain no odd subcycles.^[2] Moreover,

C_n

is triangle-free for

n > 3

, as the smallest cycle length is

n

, precluding any 3-cycles.^[15] The adjacency matrix

A

C_n

is an

n \times n

circulant matrix whose first row is

[0, 1, 0, \dots, 0, 1]

, with subsequent rows obtained by cyclic shifts; this encodes the connections to immediate neighbors.^[14] For example, in

C_5

, it takes the form

A = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}.

0100110100010100010110010

. ^[2]

Connectivity and Cycles

The cycle graph

C_n

for

n \geq 3

exhibits vertex connectivity

\kappa(C_n) = 2

, indicating that it remains connected after the removal of any single vertex but can be disconnected by the removal of two vertices. This property arises because, for any pair of distinct vertices in

C_n

, there are exactly two internally vertex-disjoint paths connecting them—the two complementary arcs along the cycle—ensuring no single vertex removal severs all paths between non-adjacent vertices. By Menger's theorem, which equates the minimum number of vertices separating two non-adjacent vertices to the maximum number of internally vertex-disjoint paths between them,

\kappa(C_n) = 2

; specifically, removing two non-adjacent vertices splits the graph into two disjoint path components, while removing two adjacent vertices leaves a single path.^[16]^[17] The edge connectivity of

C_n

is likewise

\lambda(C_n) = 2

, matching its minimum degree of 2 and confirming the absence of bridges (edges whose removal disconnects the graph). A minimum edge cut consists of two adjacent edges incident to the same vertex, or two non-adjacent edges that separate the cycle into two components; this renders

C_n

2-edge-connected, meaning it withstands the failure of any single edge while maintaining connectivity.^[17] In terms of cycle substructures, the girth of

C_n

—the length of its shortest cycle—is precisely

n

, as the graph contains only one cycle and no chords or smaller circuits. No proper subgraph of

C_n

contains a cycle, so all cycles in

C_n

are Hamiltonian and of length

n

. Every connected proper subgraph of

C_n

is a path, reflecting its 2-regular structure; for instance, the induced subgraph on any

k

consecutive vertices (

1 \leq k < n

) is the path graph

P_k

. Removing a single vertex from

C_n

produces the connected path

P_{n-1}

, while removing two non-adjacent vertices yields two disjoint paths whose lengths sum to

n-2

.^[17]

Algebraic and Spectral Properties

Automorphism Group

The automorphism group of the cycle graph

C_n

for

n \geq 3

, denoted

\mathrm{Aut}(C_n)

, is isomorphic to the dihedral group

D_n

of order

2n

. This group consists of

n

rotations generated by a cyclic shift of the vertices and

n

reflections that reverse the orientation of the cycle. The order of the automorphism group is given by

|\mathrm{Aut}(C_n)| = 2n.

^[18]^[19] The dihedral group

D_n

is generated by a rotation

\rho

of order

n

, defined by

\rho(v_i) = v_{i+1 \mod n}

for vertices labeled

v_0, \dots, v_{n-1}

, and a reflection

\sigma

of order 2, such as

\sigma(v_i) = v_{n-i \mod n}

, which fixes a vertex and the midpoint of the opposite edge (or two opposite vertices for even

n

). These generators satisfy the relation

\sigma \rho \sigma = \rho^{-1}

, capturing the symmetries of a regular

n

-gon.^[19] The action of

\mathrm{Aut}(C_n)

is vertex-transitive, as rotations map any vertex to any other, and arc-transitive, as the full dihedral action permutes both directed and undirected edges transitively while preserving adjacency. This high degree of symmetry reflects the regularity of

C_n

, where every vertex has degree 2.^[20] Cycle graphs

C_n

are uniquely determined up to isomorphism by their degree sequence—all vertices of degree 2—for each

n \geq 3

, as any connected 2-regular graph is a cycle. However, for

n=4

C_4

is isomorphic to the complete bipartite graph

K_{2,2}

, both sharing the same degree sequence and automorphism group

D_4

.^[21]^[22]

Eigenvalues and Spectrum

The adjacency matrix

A

of the cycle graph

C_n

is circulant, with 1s in the positions corresponding to edges between consecutive vertices (positions 1 and

n-1

in the generating vector). The eigenvalues of such circulant matrices are derived using the discrete Fourier transform, where the

k

-th eigenvalue is obtained by evaluating the generating polynomial at the

n

-th roots of unity:

\lambda_k = \omega^k + \omega^{-k}

, with

\omega = e^{2\pi i / n}

, simplifying to

\lambda_k = 2 \cos(2\pi k / n)

for

k = 0, 1, \dots, n-1

.^[23] The spectrum of

A

consists of these

n

real eigenvalues, which are symmetric around 0 due to the pairing

\lambda_k = \lambda_{n-k}

. The largest eigenvalue is

\lambda_0 = 2

, which is simple and corresponds to the all-ones eigenvector, reflecting the graph's regularity of degree 2.^[23] Most eigenvalues have multiplicity 2 from these pairs, except

\lambda_0 = 2

(multiplicity 1); if

n

is even,

\lambda_{n/2} = -2

also has multiplicity 1.^[23] The Laplacian matrix

L = 2I - A

C_n

inherits the circulant structure, yielding eigenvalues

\mu_k = 2 - 2 \cos(2\pi k / n)

for

k = 0, 1, \dots, n-1

.^[24] The smallest eigenvalue is

\mu_0 = 0

, simple with all-ones eigenvector, while the others are positive, confirming connectivity. The algebraic connectivity, defined as the second-smallest Laplacian eigenvalue

\mu_1 = 2 - 2 \cos(2\pi / n)

, quantifies the graph's expansion and robustness to disconnection; it approximates

(2\pi / n)^2

for large

n

and increases monotonically with

n

.^[25]^[26]

Directed Cycle Graphs

Definition

A directed cycle graph

\vec{C_n}

(also known as an oriented cycle graph) is a directed graph consisting of $n$ vertices labeled $v_1, v_2, \dots, v_n$ and $n$ directed edges that form a single directed cycle: $v_1 \to v_2 \to \dots \to v_n \to v_1$ .^[27]^[28] This structure arises as the directed analogue of the undirected cycle graph $C_n$ , where edges lack inherent direction.^[1] In $\vec{C_n}$

, every vertex has in-degree 1 and out-degree 1, as each vertex receives exactly one incoming arc and sends exactly one outgoing arc along the cycle.^[28] The graph is strongly connected, meaning there exists a directed path from every vertex to every other vertex by traversing the cycle.^[28] Unlike undirected cycle graphs, where edges are bidirectional, the arcs in a directed cycle graph impose a unidirectional traversal, preventing reverse paths without additional edges.^[27] The smallest directed cycle graph is $\vec{C_3}$

, forming a directed triangle with vertices $v_1 \to v_2 \to v_3 \to v_1$ .^[28]

Properties

A directed cycle graph

\vec{C}_n

n on $n$ vertices, where edges are oriented consistently in one direction, is strongly connected, meaning there exists a directed path from every vertex to every other vertex. Unlike the undirected cycle graph $C_n$ , which is merely connected, the directed version ensures one-way reachability along the cycle. The diameter of $\vec{C}_n$

n is $n-1$ , representing the maximum shortest directed path length between any pair of vertices, such as traversing almost the full cycle from one vertex to its predecessor.^[29]^[17] Every vertex in $\vec{C}_n$

n has uniform in-degree and out-degree of 1, distinguishing it from potentially irregular orientations of cycles. This balance, combined with strong connectivity, implies that $\vec{C}_n$

n is Eulerian in the directed sense: it possesses a directed Eulerian circuit that traverses each arc exactly once, namely the cycle itself.^[17] For arc coloring—assigning colors to arcs such that no two arcs sharing a common tail or head receive the same color—the chromatic number of $\vec{C}_n$

n is 1, as each vertex has at most one outgoing and one incoming arc. In contrast, the chromatic number of the underlying undirected graph is 2 if $n$ is even and 3 if $n$ is odd, matching that of $C_n$ .^[30]^[17] The automorphism group of $\vec{C}_n$

n is the cyclic group of order $n$ , generated by rotations along the cycle; unlike the dihedral group of the undirected $C_n$ , reflections are excluded due to the fixed edge orientations.^[18] The adjacency matrix of $\vec{C}_n$

n is circulant, featuring 1's on the superdiagonal and in the bottom-left position (n,1), with 0's elsewhere: $A = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 \end{pmatrix}$

00⋮0110⋮0001⋮00⋯⋯⋱⋯⋯00⋮0000⋮10

^[17] $\vec{C_n}$

contains a single directed cycle following the arc orientations, with no directed cycles possible in the opposite direction.^[17]

History

Media collections

Cycle graph

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Cycle graph

Terminology

Properties

Directed cycle graph

See also

References

Sources

External links

Cycle graph

Definition and Notation

Formal Definition

Notation and Examples

Add your contribution

Related Hubs

Contribute something