Search

Given two positive integers l and m , with l ? m , an l , m ] -covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l ? | M | ? m for every M ? M .An l , m ] -covering M of G is an excessive l , m ] -factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive l , m ] -factorization of G (or ∞ , if G does not admit an excessive l , m ] -factorization) is a graph parameter called the excessive l , m ] -index of G and denoted by ? l , m ] ' ( G ) . In this paper we study such parameter. Our main result is a general formula for the excessive l , m ] -index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes ? l , m ] ' ( G ) for any fixed constants l and m and outputs an excessive l , m ] -factorization of G , whenever the latter exists.

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set of factors. In the Hamiltonian case the only possibility is the unique factorization of K5, while in the non-Hamiltonian case we give some classes of examples and some necessary conditions for the existence of such factorizations.

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting primitively on the set of vertices. If F consists of Hamiltonian cycles, then F is the unique, up to isomorphisms, 2-factorization of Kpn admitting an automorphism group which acts 2-transitively on the vertex-set, see [A. Bonisoli, M. Buratti, G. Mazzuoccolo, Doubly transitive 2-factorizations, J. Combin. Designs 15 (2007) 120–132.]. In the non-Hamiltonian case we construct an infinite family of examples whose automorphism group does not contain a subgroup acting 2-transitively on vertices.