On the excessive [m] [ m ] -index of a tree
The excessive [m] [ m ] -index of a graph G G , denoted by ? [ m ] ? ( G ) , is the minimum number of matchings of size m m needed to cover the edge-set of G G . We set ? [ m ] ? ( G ) = ? if such a cover does not exist and we call a graph G G [m] [ m ] -coverable if its excessive [m] [ m ] -index is finite. Obviously ? [ 1 ] ? ( G ) = | E ( G ) | and it is easy to prove for a [2] [ 2 ] -coverable graph G G that ? [ 2 ] ? ( G ) = max { ? ? ( G ) , ? | E ( G ) | / 2 ? } holds, where ??(G) ? ? ( G ) denotes the chromatic index of G G . The case m=3 m = 3 is completely solved in Cariolaro and Fu (2009) [4]. In this paper we prove a general formula for computing the excessive [4] [ 4 ] -index of a tree and we conjecture a possible generalization for any value of m m . Furthermore, we prove that such a formula does not work for the excessive [4] [ 4 ] -index of an arbitrary graph.
trees matchings excessive index caterpillars