Cycle decomposition (graph theory)

For the notation used to express permutations, see Cycle decomposition (group theory).

In graph theory, a cycle decomposition is a partitioning of the vertices of a graph into subsets, such that the vertices in each subset lie on a cycle.

Definition

References

• Bondy, J.A.; Murty, U.S.R. (2008), "2.4 Decompositions and coverings", Graph Theory, Springer, ISBN 978-1-84628-969-9 .

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Graph theory Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Cycle cover Cycle double cover Look at other dictionaries: Cycle decomposition — In mathematics, the term cycle decomposition can mean: In graph theory, a cycle decomposition is a partitioning of the vertices of a graph into subsets, such that the vertices in each subset lie on a cycle. In group theory, a cycle decomposition… …   Wikipedia Cycle notation — For the cyclic decomposition of graphs, see Cycle decomposition (graph theory). For cycling terminology, see glossary of bicycling. In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of …   Wikipedia Neighbourhood (graph theory) — A graph consisting of 6 vertices and 7 edges For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non mathematical neighbourhoods, see Neighbourhood (disambiguation). In graph theory, an adjacent vertex of a… …   Wikipedia List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… …   Wikipedia Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia Cycle double cover — Unsolved problems in mathematics Does every bridgeless graph have a multiset of cycles covering every edge exactly twice? …   Wikipedia Cycle rank — In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a …   Wikipedia Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”