Dipartimento di Scienze di Base e Applicate per l'Ingegneria

A one-factorization of a graph G is a collection F={F_1,F_2,...,F_t} of edge-disjoint "one-factors", each being a spanning 1-regular subgraph of G. An obvious necessary condition for the existence of one-factorization is that G is regular and order of G is even. Results on sufficient conditions for the existence of one-factorizations will be presented. Moreover, various methods for constructing one-factorizations of complete graphs and complete bipartite graphs, together with their relationship to other combinatorial objects and applications, will be discussed. There are many interesting classes of one-factorizations with additional properties. One of my favorite concerns uniformness. A one-factorization F is "uniform" if the union of any two one-factors is isomorphic to the same two-factor H, which is a disjoint union of even cycles. If H is a single cycle then F is called "perfect". There are only a few infinite classes of known uniform (perfect) one-factorizations of complete graphs and only other several single examples. An opposite property may be dealt with; one can ask about the existence of one-factorization such that the union of any two one-factors does not include cycles of given lengths. A one-factorization F is said "k-cycle free" if the union of any two one-factors does not include the cycle C_k as a component. Consequently, F is "k^*-cycle free" if the union of any two one-factors does not include all cycles of lengths not exceeding k. It is proved that for every n>2 and every even k>3, where k differs from 2n, there exists a k-cycle free one-factorization of the complete graph K_{2n}. Moreover, some infinite classes of k^*-cycle free one-factorizations of K_{2n} are constructed