|
|
|
| Oriented graphs of the bipartite graph under degree |
| ZHANG Xue-fei, ZHENG Su-wen, XIA Jing, CAO Yi-peng, XU Fei |
| Basic Education Department, Army Academy of Armored Forces, Beijing 100072, China |
|
|
|
Abstract 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 has known that if the in-degree of each vertex in an oriented
graph of Kn;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 Kn;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 Kn;n such that the in-degree of each vertex is a or b. This paper shows that the
necessary condition is also su±cient for a complete bipartite graph K_{n;n}.
|
|
Published: 05 July 2019
|
|
|
度条件下的二部图的定向图
二部图是具有二分类(X; Y )的简单偶图, 其中X的每个顶点与Y 的每个顶
点相连, 若jXj = m, jY j = n, 则这样的图记为Km;n. 该文研究了Kn;n的定向图.
对于非负整数a和b, 若存在满足每个顶点的入度或者是a或者是b的一个Kn;n的定向
图, 则存在非负整数s和t满足方程s + t = 2n 和as + bt = n2. 论文证明了如下结论:
设s和t是任意两个非负整数, 对于满足方程s + t = 2n和as + bt = n2的非负整数a和b,
存在Kn;n的定向图使得每个顶点的入度或者是a或者是b, 从而得到了上述必要条件
为Kn;n是[a; b]n可实现的充分条件.
关键词：
完全二部图,
定向,
入度,
算法
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
