首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号