Namespaces
Variants
Actions

Difference between revisions of "Factorization"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (links)
(gather refs)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{TEX|done}}{{MSC|05C70}}
 
{{TEX|done}}{{MSC|05C70}}
 +
 
''in graph theory''
 
''in graph theory''
  
The decomposition of a [[Graph|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.
+
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 [[Regular graph|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.
 
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.
Line 11: Line 12:
  
 
where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.
 
where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR></table>
 
 
 
  
 
====Comments====
 
====Comments====
Line 24: Line 20:
 
====References====
 
====References====
 
<table>
 
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top"> J. Petersen,   "Die theorie der regulären Graphen"  ''Acta. Math.'' , '''15'''  (1891)  pp. 193–220</TD></TR>
+
<TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top"> W.T. Tutte,   "Graph factors"  ''Combinatorica'' , '''1'''  (1981)  pp. 79–97</TD></TR>
+
<TR><TD valign="top">[a1]</TD> <TD valign="top"> J. Petersen, "Die theorie der regulären Graphen"  ''Acta. Math.'' , '''15'''  (1891)  pp. 193–220 {{ZBL|23.0115.03}}</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top"> J. Akiyama,   M. Kano,   "Factors and factorizations of graphs - a survey"  ''J. Graph Theory'' , '''9'''  (1985)  pp. 1–42</TD></TR>
+
<TR><TD valign="top">[a2]</TD> <TD valign="top"> W.T. Tutte, "Graph factors"  ''Combinatorica'' , '''1'''  (1981)  pp. 79–97</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top"> J. Akiyama, M. Kano, "Factors and factorizations of graphs - a survey"  ''J. Graph Theory'' , '''9'''  (1985)  pp. 1–42</TD></TR>
 
</table>
 
</table>

Latest revision as of 19:41, 21 March 2024

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$.

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

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[a1] J. Petersen, "Die theorie der regulären Graphen" Acta. Math. , 15 (1891) pp. 193–220 Zbl 23.0115.03
[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=37071
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article