An Algorithm for the Orientation of Complete Bipartite Graphs
Lingqi Zhao, Mujiangshan Wang, Xuefei Zhang, Yuqing Lin, Shiying Wang · 2017
Let G be a graph with vertex set ( ) V G and edge set( ) E G .We consider the problem of orienting the edges of a complete bipartite graph , n n K so only two different in-degrees a and b occur.An obvious necessary condition for orienting the edges of G so that only two in-degrees a and b occur, is that there exist positive integers s and t satisfying | ( )| s t V G and | ( )| as bt E G .In this paper, we show that the necessary condition is also sufficient for a complete bipartite graph , n n K .Furthermore, we give the algorithms of orientations with only two in-degrees of , n n K .