The Excessive [3]-Index of All Graphs - Cariolaro, David; Fu, Hung-Lin (The Electronic Journal of Combinatorics, 2009)
Let m be a positive integer and let G be a graph. A set M of matchings of G, all of which of size m, is called an [m]-covering of G if _MM M=E(G). G is called [m]-coverable if it has an [m]-covering. An [m]-covering M such that |M | is minimum is called an excessive [m]-factorization of G and the number of matchings it contains is a graph parameter called excessive [m]-index and denoted by χ’_[m](G) (the value of χ’_[m](G) is conventionally set to ∞ if G is not [m]-coverable). It is obvious that χ’_[1](G)=|E(G)| for every graph G, and it is not difficult to see that χ’_[2](G)={χ’(G),|E(G)|/2 ceil} for every [2]-coverable graph G. However the task of determining χ’_[m](G) for arbitrary m and G seems to increase very rapidly in difficulty as m increases, and a general formula for m≥ 3 is unknown. In this paper we determine such a formula for m=3, thereby determining the excessive [3]-index for all graphs.