One-factorization
of a graph
If is a graph, then a factorization of
is a set of spanning subgraphs of
that are pairwise edge-disjoint (i.e., no two have a common edge) and whose union is all of
. A one-factorization of
is a decomposition of the edge-set of
into edge-disjoint one-factors (cf. One-factor).
In order to have a one-factorization, a graph must have an even number of vertices and must be regular: if decomposes into
disjoint one-factors, then every vertex of
must lie on precisely
edges. These conditions are not sufficient, since there is the following theorem: A regular graph with a bridge (cf. One-factor) cannot have a one-factorization (except for the trivial case where the graph is itself a one-factor).
If the degree increases with the number of vertices, the situation is different. It has been conjectured that a regular graph with vertices and degree greater than
will always have a one-factorization; this has only been proved in a very few cases, such as degree
, degree
, and degree at least
, [a7], [a20]. On the other hand, there are regular graphs with degree near to half the number of vertices and without one-factorizations.
One can prove the existence of one-factorizations in many classes of graphs. Of basic importance are the complete graphs. The complete graph has a one-factorization for all
. The
-vertex cycle
has a one-factorization if and only if
is even. The regular complete bipartite graph
(cf. Graph, bipartite) always has a one-factorization. One-factorizations of complete bipartite graphs are equivalent to Latin squares (cf. Latin square).
Some other factorizations of complete graphs are important. A near-one-factor in is a set of
edges which cover all but one vertex. A set of near-one-factors which covers every edge precisely once is called a near-one-factorization.
has a near-one-factorization for every
. It is in fact obvious that any near-one-factorization of
can be converted to a one-factorization of
by adding a vertex
and joining
to the isolated vertex in each factor. It follows that each vertex appears precisely once as an isolate in a near-one-factorization. (This also follows immediately by adding degrees.)
Theoretical considerations aside, it is often important to be able to construct a one-factorization (or a set of one-factorizations) of , for a particular value
. A hill-climbing algorithm was described by J.H. Dinitz and D.R. Stinson [a10]. In order to use the hill-climbing approach, it is necessary to formulate the search for a one-factorization as an optimization problem. One first defines a matching to be a set
of pairs of the form
, where each edge
of
occurs as the latter entry in at most one of the pairs, and where
contains no two pairs
and
with
. The cost
of a matching
is
. Then
is a one-factorization if and only if
. There is no guarantee that repeated applications of these heuristics will produce a one-factorization; however, Dinitz and Stinson [a10] report no failures in over a million trials.
A starter in an Abelian group of order
is an ordered partition of the non-zero members of
into
-sets
with the property that the
differences
are all different and therefore contain every non-zero element of
precisely once. From a starter
one constructs a set of
factors by systematically adding elements of
to
. This process is called developing
in
. Many useful small examples of one-factorizations are constructed using starters. The starter consisting of all the pairs
, where
ranges through the non-zero elements of some group, is called a patterned starter.
There is only one one-factor in , and it (trivially) constitutes the unique one-factorization. Similarly,
has just three one-factors, and together they form a factorization. There are six different one-factorizations of
,
of
,
of
[a11], and
of
[a9]; no larger numbers are known.
Two one-factorizations and
of
, say
![]() |
are called isomorphic if there exists a mapping from the vertex-set of
onto itself such that
![]() |
where is the set of all edges
, where
is an edge in
. There is a unique one-factorization of
, up to isomorphism, for
. There are exactly six for
[a8],
of
; they are listed in [a11] (see also [a12]) and
isomorphism classes of one-factorizations of
[a9]. To discuss isomorphism of factorizations, various invariants have been used. The number of isomorphism classes of one-factorizations of
tends to infinity as
does [a4], [a16].
An object whose only automorphism is the identity is called rigid or asymmetric. There are no rigid one-factorizations on ,
,
, or
points. However, there is a rigid one-factorization of
whenever
. In fact, the number of isomorphism classes of rigid one-factorizations of
goes to infinity with
.
A one-factorization is called perfect if the union of any two factors is a Hamilton cycle (cf. Hamiltonian tour). Perfect one-factorizations exist for many orders, and no order (greater than 1) is known for which no perfect one-factorization of
exists, but the existence question is not yet (1996) settled.
The following theorem holds [a2], [a3]: If is an odd prime, then
and
have perfect factorizations.
Apart from these two constructions, all other known perfect one-factorizations have been found by ad-hoc methods, using starters.
Various techniques have been studied which produce a new graph from two given graphs. There is some interest in the following problems: Given a form of graph product, what conditions on graphs and
imply that the product of
and
has a one-factorization? This has been studied for Cartesian products, wreath products and tensor products. References include [a1], [a13], [a14], [a15], [a19], [a23], [a27].
One-factorizations are frequently used to schedule sporting tournaments. One considers a graph whose vertices are competing teams; an edge indicates that the two teams must play against each other. The set of games held simultaneously is called a round. Suppose each team must compete in every round. Clearly, the games that form a round form a one-factor in the underlying graph. If a round robin tournament for teams is to be played in the minimum number of sessions, one requires a one-factorization of
. If there are
teams, the relevant structure is a near-one-factorization of
. In each case the factorization is called the schedule of the tournament.
Papers on this application include [a5], [a21], [a22], [a24], [a28], [a29], [a30].
Some general surveys on one-factorizations are [a18], [a25] and [a26]. Books on related topics include [a6] and [a17].
References
[a1] | B. Alspach, J.C. George, "One-factorization of tensor products of graphs" , Topics in Combinatorics and Graph Theory , Physica-Verlag (1990) pp. 41–46 |
[a2] | B.A. Anderson, "Finite topologies and Hamiltonian paths" J. Combin. Th. , 14B (1973) pp. 87–93 |
[a3] | B.A. Anderson, "Symmetry groups of some perfect one-factorization of complete graphs" Discrete Math. , 18 (1977) pp. 227–234 |
[a4] | B.A. Anderson, M.M. Barge, D. Morse, "A recursive construction of asymmetric ![]() |
[a5] | A.F. Beecham, A.C. Hurley, "A scheduling problem with a simple graphical solution" J. Austral. Math. Soc. , 21B (1980) pp. 486–495 |
[a6] | J. Bosák, "Decomposition of graphs" , Kluwer Acad. Publ. (1990) |
[a7] | A.G. Chetwynd, A.J.W. Hilton, "Regular graphs of high degree are ![]() |
[a8] | L.E. Dickson, F.H. Safford, "Solution to problem ![]() |
[a9] | J.H. Dinitz, D.K. Garnick, B.D. McKay, "There are ![]() ![]() |
[a10] | J.H. Dinitz, D.R. Stinson, "A hill-climbing algorithm for the construction of one-factorizations and room squares" SIAM J. Algebraic Discrete Methods , 8 (1987) pp. 430–438 |
[a11] | E.N. Gelling, "On one-factorizations of a complete graph and the relationship to round-robin schedules" Ph.D. Thesis, Univ. Victoria, Canada (1973) |
[a12] | E.N. Gelling, R.E. Odeh, "On ![]() |
[a13] | P.E. Himelwright, J.E. Williamson, "On ![]() |
[a14] | P. Himelwright, W.D. Wallis, J.E. Williamson, "On one-factorizations of compositions of graphs" J. Graph Th. , 6 (1982) pp. 75–80 (Erratum: J. Graph Theory 8 (1984), 185–186) |
[a15] | A. Kotzíg, "![]() |
[a16] | C.C. Lindner, E. Mendelsohn, A. Rosa, "On the number of ![]() |
[a17] | L. Lovász, M.D. Plummer, "Matching theory" , North-Holland (1986) |
[a18] | E. Mendelsohn, A. Rosa, "One-factorizations of the complete graph -- a survey" J. Graph Th. , 9 (1985) pp. 43–65 |
[a19] | E.T. Parker, "Edge-coloring numbers of some regular graphs" Proc. Amer. Math. Soc. , 37 (1973) pp. 423–424 |
[a20] | A. Rosa, W.D. Wallis, "Premature sets of ![]() |
[a21] | K.G. Russell, "Balancing carry-over effects in round robin tournaments" Biometrika , 67 (198) pp. 127–131 |
[a22] | T.H. Straley, "Scheduling designs for a league tournament" Ars Combin. , 15 (1983) pp. 193–200 |
[a23] | W.D. Wallis, "One-factorizations of wreath products" , Combinatorial Mathematics VIII , Lecture Notes in Mathematics , 884 , Springer (1981) pp. 337–345 |
[a24] | W.D. Wallis, "A tournament problem" J. Austral. Math. Soc. , 24B (1983) pp. 289–291 |
[a25] | W.D. Wallis, "One-factorizations of complete graphs" , Contemporary Design Theory , Wiley (1992) pp. 593–631 |
[a26] | W.D. Wallis, "One-factorizations" , Kluwer Acad. Publ. (1997) |
[a27] | W.D. Wallis, Z. Wang, "On one-factorizations of cartesian products" Congressus Numerantium , 49 (1985) pp. 237– 245 |
[a28] | D. de Werra, "Scheduling in sports" , Studies on Graphs and Discrete Programming , North-Holland (1981) pp. 381–395 |
[a29] | D. de Werra, "On the multiplication of divisions: the use of graphs for sports scheduling" Networks , 15 (1985) pp. 125–136 |
[a30] | D. de Werra, L. Jacot-Descombes, P. Masson, "A constrained sports scheduling problem" Discrete Appl. Math. , 26 (1990) pp. 41–49 |
One-factorization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=One-factorization&oldid=14412