Hubbry Logo
Cycle (graph theory)Cycle (graph theory)Main
Open search
Cycle (graph theory)
Community hub
Cycle (graph theory)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Cycle (graph theory)
Cycle (graph theory)
Cycle (graph theory)
View on Wikipedia
from Wikipedia
A graph with edges colored to illustrate a closed walk, H–A–B–A–H, in green; a circuit which is a closed walk in which all edges are distinct, B–D–E–F–D–C–B, in blue; and a cycle which is a closed walk in which all vertices are distinct, H–D–G–H, in red.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.

Definitions

[edit]

Circuit and cycle

[edit]
  • A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).[1]
Let G = (V, E, Φ) be a graph. A circuit is a non-empty trail (e1, e2, ..., en) with a vertex sequence (v1, v2, ..., vn, v1).
  • A cycle or simple circuit is a circuit in which only the first and last vertices are equal.[1]
  • n is called the length of the circuit resp. length of the cycle.

Directed circuit and directed cycle

[edit]
  • A directed circuit is a non-empty directed trail in which the first and last vertices are equal (closed directed trail).[1]
Let G = (V, E, Φ) be a directed graph. A directed circuit is a non-empty directed trail (e1, e2, ..., en) with a vertex sequence (v1, v2, ..., vn, v1).
  • A directed cycle or simple directed circuit is a directed circuit in which only the first and last vertices are equal.[1]
  • n is called the length of the directed circuit resp. length of the directed cycle.

Chordless cycle

[edit]
In this graph the green cycle A–B–C–D–E–F–A is chordless whereas the red cycle G–H–I–J–K–L–G is not. This is because the edge {K, I} is a chord.

A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A chordal graph, a special type of perfect graph, has no holes of any size greater than three.

The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth.

A peripheral cycle is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.

Cycle space

[edit]

The term cycle may also refer to an element of the cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the binary cycle space (usually called simply the cycle space), which consists of the edge sets that have even degree at every vertex; it forms a vector space over the two-element field. By Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space.[2]

Using ideas from algebraic topology, the binary cycle space generalizes to vector spaces or modules over other rings such as the integers, rational or real numbers, etc.[3]

Cycle detection

[edit]

The existence of a cycle in directed and undirected graphs can be determined by whether a depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains a back edge).[4] All the back edges which DFS skips over are part of cycles.[5] In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.[5]

For directed graphs, distributed message-based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.[6]

Algorithm

[edit]

The aforementioned use of depth-first search to find a cycle can be described as follows: 

For every vertex v: visited(v) = finished(v) = false
For every vertex v: DFS(v)

where 

DFS(v) =
  if finished(v): return
  if visited(v):
    "Cycle found"
    return
  visited(v) = true
  for every neighbour w: DFS(w)
  finished(v) = true

For undirected graphs, "neighbour" means all vertices connected to v, except for the one that recursively called DFS(v). This omission prevents the algorithm from finding a trivial cycle of the form v→w→v; these exist in every undirected graph with at least one edge.

A variant using breadth-first search instead will find a cycle of the smallest possible length.

Covering graphs by cycle

[edit]

In his 1736 paper on the Seven Bridges of Königsberg,[7] widely considered to be the birth of graph theory,[8][9] Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex.[7] The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an Eulerian trail. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem.[10] When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem.

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete.[11] Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.[12]

The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.[13]

Graph classes defined by cycle

[edit]

Several important classes of graphs can be defined by or characterized by their cycles. These include:

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Cycle (graph theory)

View on Grokipedia
from Grokipedia
In graph theory, a cycle is a closed walk with no repeated vertices or edges except for the starting and ending vertex, which are the same; the length of a cycle is the number of its edges, and it must contain at least three vertices to avoid degenerate cases like multiple edges between two vertices. Cycles are distinguished from more general circuits (closed trails that may repeat vertices) by the absence of repeated internal vertices, ensuring they form simple, non-redundant loops in the graph. In directed graphs, a cycle follows a consistent orientation along its edges, forming a directed closed path. Cycles play a central role in characterizing graph properties and structures. A graph is bipartite if and only if it contains no odd-length cycles, a theorem that underpins algorithms for and partitioning. The absence of cycles defines acyclic graphs, which are forests if disconnected and if connected, with exactly v−1v-1 edges for vv vertices; adding any edge to a tree creates a unique cycle. Special cases include Hamiltonian cycles, which visit every vertex exactly once and are NP-complete to detect, and Eulerian cycles, which traverse every edge exactly once in graphs where all vertices have even degree. The cycle space of a graph is the over GF(2) generated by the edge sets of its cycles, with equal to the number of edges minus vertices plus connected components, enabling linear algebraic approaches to problems like finding minimum cycle bases for analysis. Cycles also feature prominently in via Kuratowski's theorem, which states a graph is planar if it contains no subdivision of K5K_5 or K3,3K_{3,3}, both of which involve cycles. Applications extend to optimization, such as the for efficient routing via Eulerian augmentations, deadlock detection in operating systems, and network flow computations.

Definitions and Variants

Undirected Cycles and Circuits

In undirected graphs, a walk is a finite sequence of vertices and edges v0,e1,v1,e2,…,ek,vkv_0, e_1, v_1, e_2, \dots, e_k, v_k, where each edge eie_i connects vertices vi−1v_{i-1} and viv_i, and vertices and edges may repeat. A is a walk with no repeated edges, while a path is a trail with no repeated vertices (except possibly the endpoints if considering closed variants, though typically paths are open). A circuit is a closed trail, meaning it starts and ends at the same vertex and has no repeated edges, but vertices other than the start and end may repeat. A cycle is a closed path, defined as a circuit in which no vertices are repeated except the starting and ending vertex, ensuring no repeated vertices or edges overall. This distinguishes cycles from more general circuits, which permit repeated internal vertices as long as edges remain distinct; cycles thus represent the simplest form of closed structures without redundancy in vertices. For example, in the complete graph K3K_3—a triangle formed by three vertices each connected by an edge—the sequence of all three vertices and their edges forms the smallest possible cycle of length 3. Formally, a cycle CC of length k≥3k \geq 3 is denoted as the sequence v1,e1,v2,…,ek,v1v_1, e_1, v_2, \dots, e_k, v_1, where the vertices v1,v2,…,vkv_1, v_2, \dots, v_k are distinct and the edges e1,…,eke_1, \dots, e_k are distinct, with each eie_i incident to viv_i and vi+1v_{i+1} (and eke_k to vkv_k and v1v_1).

Directed Cycles

In directed graphs, also known as digraphs, the concepts of walks, trails, paths, and circuits are adapted to account for the orientation of edges, referred to as . A directed walk is a finite non-null sequence of vertices and v0,a1,v1,…,ak,vkv_0, a_1, v_1, \dots, a_k, v_k, where each arc aia_i has vi−1v_{i-1} and head viv_i for i=1,…,ki = 1, \dots, k. A directed is a directed walk with no repeated . A directed path is a directed with no repeated vertices. A directed circuit is a closed directed , that is, a directed in which the initial and terminal vertices coincide. A directed cycle is a directed circuit in which no vertex is repeated except the initial and terminal ones, which are the same; it must contain at least one arc. This distinguishes it from a directed circuit, which permits repeated vertices (other than the endpoints) as long as no arc is repeated. Formally, a directed cycle can be denoted as a sequence of distinct vertices v1,v2,…,vkv_1, v_2, \dots, v_k (with k≥2k \geq 2) such that there are directed arcs from viv_i to vi+1v_{i+1} for i=1,…,k−1i = 1, \dots, k-1, and from vkv_k to v1v_1. A simple example of a directed cycle is a directed in a tournament graph, where three vertices a,b,ca, b, c are connected by arcs a→ba \to b, b→cb \to c, and c→ac \to a, forming a cyclic orientation without any transitive relations among them. In the context of digraph connectivity, a with more than one vertex necessarily contains at least one directed cycle, as mutual implies cyclic paths.

Structural Properties

Chordless Cycles

In , a chord of a cycle is an edge that connects two non-consecutive vertices of the cycle. A chordless cycle, also known as an induced cycle, is a cycle that contains no such chords, meaning the subgraph induced by its vertices consists solely of the cycle edges. When the length of the cycle is at least four, it is often specifically termed a . Chordless cycles possess the property of being minimal induced subgraphs that form cycles, as any additional edge within the vertex set would introduce a chord or alter the induced structure. For instance, the C4C_4, consisting of four vertices connected in a square, is a chordless cycle, but adding a diagonal edge between opposite vertices introduces a chord, rendering the original cycle no longer induced. Chordless cycles of length greater than three play a key role in the theory of perfect graphs, where their absence characterizes chordal graphs, a subclass of perfect graphs. By definition, every non-chordal graph contains a chordless cycle of length at least four.

Cycle Length and Girth

The length of a cycle in an undirected graph is defined as the number of edges it contains, which equals the number of vertices since the cycle returns to its starting point. This measure captures the size of the cycle as a closed path without repeated vertices except the endpoints. The girth g(G)g(G) of a graph GG is the length of its shortest cycle, formally given by g(G)=min⁡{\length(C)∣C is a cycle in G},g(G) = \min \{ \length(C) \mid C \text{ is a cycle in } G \}, or ∞\infty if GG contains no cycles (i.e., if GG is acyclic). This parameter quantifies the local cyclicity of the graph, with smaller values indicating the presence of short cycles like . For example, trees, which are connected acyclic graphs, have infinite girth by definition. In contrast, the KnK_n for n≥3n \geq 3 has girth 3, as every triple of vertices forms a , the shortest possible cycle. The distribution of cycle lengths in a graph depends on its and connectivity. In dense graphs, characterized by a high proportion of edges relative to the number of vertices (e.g., average degree Ω(n)\Omega(n)), short cycles predominate due to the abundance of local connections, while longer cycles—up to lengths approaching the order of the graph—also occur, often forming consecutive sequences from the girth onward when the minimum degree is sufficiently large. This contrasts with sparse graphs, where cycles, if present, tend to be longer and sparser in distribution. The girth provides insight into edge density constraints. Graphs with large girth must be sparse, as excessive edges tend to create short cycles; for instance, graphs with girth at least 5 have at most O(n3/2)O(n^{3/2}) edges, by the Kővári–Sós–Turán theorem. The Moore bound formalizes this for regular graphs, giving an upper limit on the number of vertices nn for a given degree dd and girth gg, such as n≤1+d+d(d−1)+⋯+d(d−1)(g−3)/2n \leq 1 + d + d(d-1) + \cdots + d(d-1)^{(g-3)/2} for odd g≥3g \geq 3, with equality achieved only in rare cases like the for g=3g=3. This bound highlights how high girth restricts growth in vertex count for fixed degree, linking cycle shortness to overall graph expansion.

Algebraic Structure

Cycle Space

In graph theory, the cycle space of an undirected graph G=(V,E)G = (V, E) is defined as the over the binary field GF(2)\mathrm{GF}(2) whose elements are the subsets of edges that form even-degree subgraphs, also known as Eulerian subgraphs. These subgraphs are precisely those where every vertex has even degree in the . Vector addition in this space is performed via the of edge sets, which corresponds to addition modulo 2 on the characteristic vectors of the edge subsets. The cycle space is generated by the simple cycles of the graph, meaning every even-degree subgraph can be expressed as a GF(2)\mathrm{GF}(2)-linear combination of simple cycles. Thus, the simple cycles serve as generating elements, and the symmetric difference of any two cycles yields another element of the space, such as a disjoint union of cycles or a more complex even subgraph. The of the cycle space is given by m−n+cm - n + c, where m=∣E∣m = |E| is the number of edges, n=∣V∣n = |V| is the number of vertices, and cc is the number of connected components of GG. This formula arises from the fact that the rank of the of GG over GF(2)\mathrm{GF}(2) is n−cn - c, making the nullity ( of the kernel, which is the cycle space) equal to m−(n−c)m - (n - c); this is a consequence of Kirchhoff's matrix-tree theorem extended to the binary field. For example, in a cycle graph CnC_n with nn vertices and nn edges, which is connected (c=1c = 1), the dimension is n−n+1=1n - n + 1 = 1, and the cycle space is spanned by the single generator consisting of all edges of the full cycle.

Basis and Dimension of Cycle Space

In the cycle space of a graph GG with mm edges, nn vertices, and cc connected components over F2\mathbb{F}_2, a basis consists of m−n+cm - n + c linearly independent cycles, known as the cyclomatic number of GG. This set of cycles generates the entire space under symmetric difference, and any larger set is linearly dependent. A standard way to construct such a basis uses fundamental cycles derived from a of GG. For a connected graph, select a TT; each of the m−(n−1)m - (n-1) edges not in TT (chords) defines a unique fundamental cycle by adding that edge to TT, forming the unique cycle in the subgraph induced by TT union the chord. In the general case with cc components, a FF has n−cn - c edges, and each of the remaining m−(n−c)m - (n - c) edges closes a unique cycle with the unique path in FF connecting its endpoints, yielding a basis of fundamental cycles. The formula arises from linear algebra applied to the of GG. Consider the n×mn \times m BB over F2\mathbb{F}_2, where rows correspond to vertices and columns to edges, with entries indicating the endpoints modulo 2. The cycle space is the kernel of BB, as cycles correspond to edge subsets with even degree at every vertex. The rank of BB equals n−cn - c, since the row space has corank cc (one dependency per component), so by the rank-nullity theorem, the nullity ( of the cycle space) is m−(n−c)m - (n - c). For example, the K4K_4 has n=4n=4, m=6m=6, and c=1c=1, so the cycle space dimension is 6−4+1=36 - 4 + 1 = 3. A with 3 edges leaves 3 chords, each defining a fundamental cycle (e.g., triangles sharing edges), forming a basis. These three 3-cycles generate all even subgraphs, including the symmetric difference yielding the outer 4-cycle. The cycle space is orthogonal to the cut space (bond space) in the edge space over F2\mathbb{F}_2, meaning their intersection is trivial and their dimensions sum to mm; every cycle meets every cut evenly. This duality underpins many algebraic results in .

Detection and Computation

Cycle Detection Algorithms

Cycle detection in graphs is a fundamental problem that determines whether a graph contains one or more cycles. In undirected graphs, the presence of a cycle can be efficiently detected using (DFS) by identifying back edges, which are edges connecting a vertex to one of its ancestors in the DFS . The algorithm proceeds by performing a DFS traversal starting from an arbitrary vertex, maintaining a visited to track explored nodes and a parent to record the traversal path. During the traversal, for each adjacent vertex of the current node, if the adjacent vertex is unvisited, it is recursively visited with the current node as its parent; if it is visited and not the parent of the current node, a back edge is detected, confirming the of a cycle. This process is repeated for all unvisited vertices to handle disconnected components. The of this DFS-based approach is O(n + m), where n is the number of vertices and m is the number of edges, as it traverses each vertex and edge exactly once. Here is pseudocode for cycle detection in an undirected graph using DFS:

boolean hasCycle(Graph G) { boolean[] visited = new boolean[G.n]; int[] parent = new int[G.n]; // Initialize to -1 for (int v = 0; v < G.n; v++) { if (!visited[v]) { if (DFS(G, v, visited, parent)) { return true; } } } return false; } boolean DFS(Graph G, int u, boolean[] visited, int[] parent) { visited[u] = true; for (int v : G.adj[u]) { if (!visited[v]) { parent[v] = u; if (DFS(G, v, visited, parent)) { return true; } } else if (v != parent[u]) { return true; // Back edge } } return false; }

boolean hasCycle(Graph G) { boolean[] visited = new boolean[G.n]; int[] parent = new int[G.n]; // Initialize to -1 for (int v = 0; v < G.n; v++) { if (!visited[v]) { if (DFS(G, v, visited, parent)) { return true; } } } return false; } boolean DFS(Graph G, int u, boolean[] visited, int[] parent) { visited[u] = true; for (int v : G.adj[u]) { if (!visited[v]) { parent[v] = u; if (DFS(G, v, visited, parent)) { return true; } } else if (v != parent[u]) { return true; // Back edge } } return false; }

This pseudocode illustrates the recursive DFS implementation, where a back edge to a non-parent visited node signals a cycle. For directed graphs, cycle detection also relies on DFS but requires distinguishing between different states of visitation to detect back edges that form cycles. Vertices are colored white (unvisited), gray (currently in the recursion stack, i.e., being explored), or black (fully explored and removed from the stack). A cycle exists if, during traversal, an edge leads to a gray vertex, indicating a back edge within the current path. The algorithm iterates over all vertices, initiating DFS from unvisited ones, and uses the color scheme to avoid false positives from cross or forward edges. Like the undirected case, the time complexity is O(n + m). Tarjan's algorithm provides an efficient method for detecting cycles in directed graphs by computing strongly connected components (SCCs) in linear time. It uses a single DFS traversal with a stack to track the recursion order and low-link values to identify SCCs; if any SCC contains more than one vertex or a self-loop, a cycle is present in the graph. This approach not only detects cycles but also partitions the graph into its SCCs, offering additional structural insight. The algorithm runs in O(n + m) time and is based on depth-first search with careful bookkeeping of discovery times and low values.

Finding Minimum Cycles

The girth of an undirected graph, defined as the length of its shortest cycle, can be computed using a (BFS)-based algorithm that identifies the minimum cycle length passing through each vertex. This approach begins by selecting a starting vertex vv and performing a from vv, constructing a while tracking distances from vv and pointers for each visited vertex. During the traversal, if an edge connects a vertex uu to a visited vertex ww that is not its in the , this indicates a non-tree edge forming a cycle of length dist(v,u)+dist(v,w)+1\mathrm{dist}(v, u) + \mathrm{dist}(v, w) + 1. The shortest such cycle length found in this represents the minimum cycle through vv. Repeating this process for every vertex vv in the graph and taking the global minimum yields the girth. The of this is O(nm)O(nm), where nn is the number of vertices and mm is the number of edges, as each of the nn BFS traversals takes O(m)O(m) time; in dense graphs where m=Θ(n2)m = \Theta(n^2), this simplifies to O(n3)O(n^3). To find not just the girth but the actual shortest cycles, the can be modified to record and reconstruct the paths from vv to uu and ww via the parent pointers, forming the cycle upon detecting the non-tree edge. Optimized variants for girth computation reduce the number of BFS starts by initiating searches only from high-degree vertices or using heuristics to prune unnecessary traversals, though the worst-case complexity remains O(nm)O(nm) for exact results. For example, in an r×cr \times c grid graph, which has girth 4 due to the smallest square subgraphs, BFS from any internal vertex will detect a 4-cycle within two layers of exploration by finding non-tree edges between adjacent rows and columns. To identify all minimum-length cycles (i.e., all cycles of girth length), one can extend enumeration techniques such as Johnson's algorithm, which systematically finds all elementary cycles in the graph. Johnson's method, originally for directed graphs but adaptable to undirected ones by treating edges as bidirectional while avoiding immediate reversals, uses a depth-first search with vertex blocking to generate cycles without repetition, running in O((n+m)(c+1))O((n + m)(c + 1)) time where cc is the number of elementary cycles. By applying it and filtering for cycles of exactly the computed girth length, all shortest cycles can be obtained, though this is efficient only if cc is not excessively large compared to nmnm.

Graph Classes and Applications

Classes Defined by Absence of Cycles

In graph theory, acyclic graphs, also known as forests, are undirected graphs that contain no cycles whatsoever. A forest is disconnected if it has multiple connected components, while a connected acyclic graph is specifically called a tree. Trees and forests are fundamental structures with numerous applications in computer science and combinatorics, such as representing hierarchical data or spanning trees in networks. For a tree with nn vertices, the number of edges is exactly n−1n-1, and more generally, a forest with nn vertices and cc connected components has n−cn - c edges. A classic example of an acyclic graph is a path graph, which connects vertices in a linear sequence without forming any loops. Bipartite graphs represent another important class defined by the absence of certain cycles, specifically those of odd length. A graph is bipartite if and only if its vertices can be partitioned into two such that every edge connects a vertex from one set to the other, making it equivalent to being 2-colorable where adjacent vertices receive different colors. The absence of odd-length cycles is a defining property: even cycles, such as a 4-cycle, are bipartite, while odd cycles, like a (3-cycle), are not. Bipartiteness can be tested efficiently using algorithms, such as , which attempts to assign colors and detects conflicts indicating an odd cycle. A foundational result states that a graph is bipartite if and only if it contains no odd cycles, a characterization that underpins many algorithmic distinctions between bipartite and non-bipartite graphs. Chordal graphs are characterized by the absence of chordless cycles of length greater than three, meaning every cycle of length at least four must contain at least one chord—an edge connecting non-adjacent vertices in the cycle. This property ensures that chordal graphs are "rigid" in a structural sense, avoiding induced long cycles that lack internal connections. Chordal graphs include trees as a subclass and are prevalent in applications like Bayesian networks and problems due to their perfect elimination orderings, which allow efficient computations. For instance, a is chordal since all potential cycles have chords, whereas a of length five is not chordal because it is chordless.

Cycle Covers and Decompositions

A cycle cover of a graph is a set of cycles such that every vertex belongs to exactly one cycle, thereby covering all vertices; alternatively, an edge cycle cover is a set of cycles that together include every edge of the graph at least once. In directed graphs, a cycle cover typically refers to a vertex-disjoint collection of directed cycles covering all vertices, which can be found efficiently using bipartite matching techniques where the minimum number of cycles equals the number of vertices minus the size of a maximum matching in the associated . The minimum cycle cover problem seeks a cycle cover with the smallest number of cycles (for vertex covers) or minimum total length/cost (for weighted variants), and in directed graphs, it is closely related to the feedback arc set problem, as both involve breaking or covering cyclic structures to achieve acyclicity or partitioning into cycles. This problem is NP-hard in undirected graphs but solvable in polynomial time for directed graphs via reduction to the assignment problem. An edge-disjoint cycle partitions the edge set of a graph into cycles with no shared edges. Such a decomposition exists the graph is Eulerian, meaning it is connected and every vertex has even degree; in this case, an Eulerian circuit can be partitioned into edge-disjoint cycles. More precisely, Veblen's theorem states that an undirected graph admits an edge-disjoint cycle every vertex has even degree, with the connectedness condition applying per component to ensure 2-regular subgraphs form proper cycles rather than isolated edges. Cycle covers and decompositions find applications in network flow analysis, where any feasible flow in a can be decomposed into a combination of path flows and circulating cycle flows, aiding in understanding flow circulation and optimization. In scheduling, such as round-robin tournaments, the edge-disjoint Hamiltonian cycle decomposition of the K2m+1K_{2m+1} (which exists and consists of mm such cycles) allows partitioning matches into mm rounds where each team plays exactly once per round. For example, K5K_5 (with 5 vertices) decomposes into 2 edge-disjoint Hamiltonian cycles, such as (1-2-3-4-5-1) and (1-3-5-2-4-1), covering all 10 edges without overlap. In oriented graphs, cycle covers can extend to directed variants for analyzing tournaments or asymmetric relations, but the core concepts align with undirected decompositions when considering underlying structures.

References

  1. https://math.arizona.edu/~kglasner/math443/BondyMurtyGTWA.pdf
  2. https://www.cs.toronto.edu/~david/course-notes/csc110-111/17-graphs/06-cycles-and-trees.html
  3. https://www.math.cmu.edu/~mradclif/teaching/241F18/CycleBases.pdf
  4. https://www.cs.cornell.edu/courses/cs4410/2015fa/slides/06-deadlocks.pdf
  5. https://mathworld.wolfram.com/GraphCycle.html
  6. https://mathworld.wolfram.com/CycleGraph.html
  7. https://www.zib.de/userpage/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf
  8. http://people.math.binghamton.edu/zaslav/Oldcourses/580.S13/blair-peyton.chordal-graphs-clique-trees.ornl1992.pdf
  9. https://arxiv.org/abs/1404.7610
  10. https://link.springer.com/article/10.1007/BF02992776
  11. https://doi.org/10.1007/978-3-0348-0597-1_4
  12. https://mathworld.wolfram.com/Girth.html
  13. https://doi.org/10.1016/j.jctb.2017.08.002
  14. https://yufeizhao.com/gtacbook/1.pdf
  15. https://mathworld.wolfram.com/MooreGraph.html
  16. https://www.cambridge.org/core/books/algebraic-graph-theory/6C70471342F19680068C35EF174075DC
  17. https://people.mpi-inf.mpg.de/~mehlhorn/ftp/SurveyCycleBases.pdf
  18. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-4-3.pdf
  19. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
  20. https://epubs.siam.org/doi/10.1137/0201010
  21. http://theory.stanford.edu/~virgi/cs267/lecture3.pdf
  22. https://people.csail.mit.edu/virgi/6.890/lecture11.pdf
  23. https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
  24. https://par.nsf.gov/servlets/purl/10314301
  25. https://arxiv.org/pdf/2105.10094
  26. https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%252075.PDF
  27. https://www.semanticscholar.org/topic/Edge-cycle-cover/4454052
  28. https://www.sciencedirect.com/science/article/pii/S030439751930297X
  29. https://epubs.siam.org/doi/10.1137/S0097539794267255
  30. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture17.pdf
  31. https://www.classes.cs.uchicago.edu/archive/2014/spring/27500-1/files/GTspring14_homework3.pdf
  32. https://dspace.mit.edu/bitstream/handle/1721.1/49424/networkflows00ahuj.pdf
  33. http://profs.ic.uff.br/~celso/artigos/2023Tournaments.pdf
  34. https://www.sciencedirect.com/science/article/pii/0095895684900200
  35. https://www.sciencedirect.com/science/article/pii/S0095895620301258
Add your contribution
Related Hubs
User Avatar
No comments yet.