度条件下的二部图的定向图
|
摘要
二部图是具有二分类(X,Y)的简单偶图,其中X的每个顶点与Y的每个顶点相连,若|X|=m,|Y|=n,则这样的图记为K_(m,n).该文研究了K_(n,n)的定向图.对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个K_(n,n)的定向图,则存在非负整数s和t满足方程s+t=2n和as+bt=n~2.论文证明了如下结论:设s和t是任意两个非负整数,对于满足方程s+t=2n和as+bt=n~2的非负整数a和b,存在K_(n,n)的定向图使得每个顶点的入度或者是a或者是b,从而得到了上述必要条件为K_(n,n)是[a,b]_n可实现的充分条件.
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 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 = 2 n 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 = 2 n 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 sufficient for a complete bipartite graph K_(n,n).
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 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 = 2 n 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 = 2 n 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 sufficient for a complete bipartite graph K_(n,n).
引文
[1] Bondy J A, Murty U S R. Graph Theory[M]. New York:Springer, 2008.
[2] Jensen J B, Gutin G. Digraphs Theory, Algorithms and Applications[M]. New York:Springer, 2007.
[3] Brian B, Deeparnab C, Prasad T. G-parking functions, acyclic orientations and spanning trees[J]. Discrete Mathematics, 2010, 310(8):1340-1353.
[4] Ido B, Michael K, Benny S. Biased orientation games[J]. Discrete Mathematics, 2012,312(10):1732-1742.
[5] Joe B, Steve B, Ron G, Eric T. Hypercube orientations with only two in-degrees[J]. Journal of Combinatorial Theory, Series A, 2011, 118(6):1695-1702.
[6]张雪飞,王世英.完全偶图的定向图[J].山东科学,2013, 26(3):1-4.
[2] Jensen J B, Gutin G. Digraphs Theory, Algorithms and Applications[M]. New York:Springer, 2007.
[3] Brian B, Deeparnab C, Prasad T. G-parking functions, acyclic orientations and spanning trees[J]. Discrete Mathematics, 2010, 310(8):1340-1353.
[4] Ido B, Michael K, Benny S. Biased orientation games[J]. Discrete Mathematics, 2012,312(10):1732-1742.
[5] Joe B, Steve B, Ron G, Eric T. Hypercube orientations with only two in-degrees[J]. Journal of Combinatorial Theory, Series A, 2011, 118(6):1695-1702.
[6]张雪飞,王世英.完全偶图的定向图[J].山东科学,2013, 26(3):1-4.