关键词: 二部图, 定向, 入度

Abstract:

A complete bipartite graph is a simple bipartite with bipartition (X,Y) if each vertex in X is connected with each vertex in Y. A complete bipartite graph is denoted as Km,n if ｜X｜=m and ｜Y｜=n.This paper addresses the oriented graphs of K_m,n, and proves that there exist two nonnegative integers s and t satisfying the equations s+t=2n and as+bt=n2  if the indegree of each vertex in an oriented graph of  Kn,nis a or b (a and b are two nonnegative integers). Moreover, there exists an oriented graph of  Kn,nthat makes the indegree of each vertex to be either a or b for the nonnegative integers a, b and n satisfying some special conditions.

Key words: bipartite graph, orientation, indegree