Namespaces
Variants
Actions

Factorization

From Encyclopedia of Mathematics
Revision as of 21:28, 11 January 2016 by Richard Pinch (talk | contribs) (layout)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05C70 [MSN][ZBL]

in graph theory

The decomposition of a graph into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree $k$ is called a $k$-factor; a $1$-factor is also called a perfect matching. A graph is called $k$-factorizable (or $k$-factorable) if it can be represented as a union of edge-disjoint $k$-factors.

In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph with the same number of vertices in each part are $1$-factorizable. A connected graph is $2$-factorizable if and only if it is a regular graph of even degree. A graph $G$ has a $1$-factor if and only if it has an even number of vertices and if there is no subset of vertices $U$ such that the number of components with an odd number of vertices of the graph $G\setminus U$, obtained from $G$ by deleting the vertices of $U$, exceeds $|U|$. Every two-connected regular graph of degree 3 can be decomposed into a $1$-factor and a $2$-factor which are edge-disjoint.

Examples of non-regular factors are spanning trees (cf. Tree) and forests, spanning planar subgraphs (see Graph imbedding), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph $G$ is equal to

$$\max_k\left\lbrace\frac{g_k}{k-1}\right\rbrace,$$

where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9


Comments

A spanning subgraph of a graph $G=(V,E)$ is a subgraph $G_1=(V_1,E_1)$ whose set of vertices $V_1$ is equal to the set of vertices $V$ of $G$.

The $1$-factor theorem quoted above is due to W.T. Tutte. Given a vertex function $f$, a factor $F$ is called an $f$-factor if $d(v|F)=f(x)$ for every $v\in V$, the vertex set of $G$. Tutte also proved an $f$-factor theorem. The results on $2$-factors mentioned above are due to J. Petersen [a1]. A comprehensive treatment of all these results is given by Tutte in [a2]. A recent survey is [a3].

References

[a1] J. Petersen, "Die theorie der regulären Graphen" Acta. Math. , 15 (1891) pp. 193–220
[a2] W.T. Tutte, "Graph factors" Combinatorica , 1 (1981) pp. 79–97
[a3] J. Akiyama, M. Kano, "Factors and factorizations of graphs - a survey" J. Graph Theory , 9 (1985) pp. 1–42
How to Cite This Entry:
Factorization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Factorization&oldid=37484
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article