×

Oriented graphs of the bipartite graph under degree. (Chinese. English summary) Zbl 1449.05125

Summary: A graph is bipartite if its vertex set can be partitioned into two subsets \(X\) and \(Y\) such that every edge has one end in \(X\) and one end in \(Y\), such a partition \( (X,Y)\) is called a bipartition of the graph. A simple bipartite graph with bipartition \( (X,Y)\) is called a complete bipartite graph if every vertex in \(X\) is adjacent to every vertex in \(Y\). Furthermore, the complete bipartite graph is denoted by \({K_{m,n}}\) if \(|X| = m\) and \(|Y| = n\). It is known that if the in-degree of each vertex in an oriented graph of \({K_{n,n}}\) is \(a\) or \(b\), where \(a\) and \(b\) are two non-negative integers, then there exist two non-negative integers \(s\) and \(t\) satisfying the equations \(s + t = 2n\) and \(as + bt = {n^2}\). This paper investigates oriented graphs of \({K_{n,n}}\), and proves the following results. Let \(s\) and \(t\) be two arbitrary non-negative integers. For two non-negative integers \(a\) and \(b\) satisfying the equations \(s + t = 2n\) and \(as + bt = {n^2}\), there exists an oriented graph of \({K_{n,n}}\) such that the in-degree of each vertex is \(a\) or \(b\). This paper shows that the necessary condition is also sufficient for a complete bipartite graph \({K_{n,n}}\).

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI