02104839

j

02104839 Volkmann, Lutz On the number of edge-disjoint almost perfect matchings in regular odd order graphs. J. Comb. Math. Comb. Comput. 50, 195-205 (2004). 2004 Charles Babbage Research Centre, Winnipeg EN almost perfect matchings regular graphs disjoint matchings In this contribution a sharp bound for the number of edge-disjoint almost perfect matchings in a regular odd order graph is presented. Here, a matching in a graph is almost perfect if every vertex with exactly one exception is incident with an edge of the matching. The main result is even slightly stronger: If $x_1,\dots, x_p$ are arbitrary given, pairwise different, vertices of the graph $G$, then there exist $p$ (with $p= \min\{{k\over 2},\lceil k-{n\over 3}\rceil\}$) pairwise edge-disjoint almost perfect matchings $M_1,\dots, M_p$ in $G$ with the property that no edge of $M_i$ is incident with $x_i$ for $i= 1,2,\dots, p$. Bert Randerath (K\"oln)