Factor (graph theory)

A 1-factor of a graph and therefore also a perfect matching

2-factor of a graph

Another 2-factor of a graph and also a Hamilton cycle

A possible 2-factorization of (the complete graph with 5 vertices) into two 2-factors (blue and red) ${\displaystyle K_{5}}$

In graph theory, a factor is a subgraph of a graph , in which certain requirements are placed on the degree of the nodes and on the relationship of the graph. Factors play an important role in the theory of the matching problem and the Hamilton circle problem .

definition

Let be a simple graph and a map that assigns a natural number to each node of the graph . A g-factor is then a subgraph of with the same set of nodes as , in which every node of has degrees , i.e. has exactly neighbors. ${\displaystyle G=(V,E)}$ ${\displaystyle g\colon V\rightarrow \mathbb {N} _{0}}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle v_{i}}$ ${\displaystyle F}$ ${\displaystyle g(v_{i})}$ ${\displaystyle g(v_{i})}$

If the condition applies to all nodes with , i.e. all nodes of the subgraph have exactly neighbors, one speaks accordingly of an a-factor . If, on the other hand, the condition applies to all nodes , i.e. all nodes of the subgraph have at least and at most neighbors, one speaks accordingly of an [a, b] factor . ${\displaystyle v_{i}}$ ${\displaystyle i=1,\ldots ,|V|}$ ${\displaystyle g(v_{i})=a}$ ${\displaystyle a}$ ${\displaystyle v_{i}}$ ${\displaystyle a\leq g(v_{i})\leq b}$ ${\displaystyle a}$ ${\displaystyle b}$

Equivalent definition

The following is equivalent to the above definition: An a- regular subgraph that spans the graph is called a-factor. ${\displaystyle G}$

Related terms

A decomposition of a graph into a-factors is called a-factorization . A non-empty graph is called factor-critical if a 1-factorization becomes possible by removing any node .

Examples

A pairing is a factor, i.e. a subgraph of in which each node has at most one neighbor. A perfect pairing , on the other hand, is a 1-factor, i.e. a subgraph of in which every node has exactly one neighbor. Finally, Hamiltonian graphs have 2-factors in which every node has exactly two neighbors. ${\displaystyle [0,1]}$ ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle x}$

Existence of factors

The one factor Tutte theorem states that one out and a graph can be constructed, which if and only has a 1-factor if one factor has. This is the definition of a reduction in the sense of theoretical computer science. Conversely, since 1-factors are special cases of -factors, the -factor problem is equivalent to the 1-factor problem. ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle G^{*}}$ ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle g}$

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).