Bipartite regulation numbers |
| |
Institution: | Western Michigan University, Kalamazoo, MI 49008, U.S.A.;Drew University, Madison, NJ 07940, U.S.A. |
| |
Abstract: | The bipartite regulation number br(G) of a bipartite graph G with maximum degree d is the minimum number of vertices required to add to G to construct a d-regular bipartite supergraph of G. It is shown that if G is a connected m-by-n bipartite graph with m ? n and n ? m ? d ? 1, then br(G) = n ? m. If. however, n ? m ? d ? 2, the br(G) = n ? m + 2l for some l satisfying 0 ? l ? d ? (n ? m). Conversely, if l, k and d (>2) are integers such that 0 ? l ? k and 2 ? k ? d, then there is an connected m-by-n bipartite graph G of maximum degree d for which br(G) = n ? m + 2l, for some m and n with k = d ? (n ?m). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|