Complete Bipartite Graph Orientations

An orientation of a graph G= （V, E） is obtained from G= （V, E） by replacing each edge{x,y} of G by either xy or yx （i.e. digraph having no 2-cycle and no loops）.At the process of orienting the graph, we can make the orientations to meet a variety of conditions. Both domestic and foreign readers have in-depth research. Buhler etc. considered the problem of orienting the edges of the n-dimensional hypercube so that only two in-degrees occur, i.e. a or b, and obtained some sufficient and necessary conditions. In this paper, we consider this kind of oriented problem for complete bipartite graphs and get the necessary and sufficient conditions so that only two in-degrees occur in the orientations.This article is divided into four chapters. The first chapter introduces the research back-ground, current situation, research content and significance and main conclusion. Readers researched the graph orientations with set connectivity requirements, the strong diameter, in-degrees and independent arcs and so on. In this paper, we study the orientations of complete bipartite graphs with only two in-degrees.The second chapter introduces some basic concepts and terminology of graph theory.The third chapter introduces the main contents of this paper. In this paper, K_n,n is oriented to a digraph so that only two in-degrees a and b occur and we get the necessary and sufficient conditions. For convenience, let [a, b]_n be a shorthand for the problem of realizing an orientation on K_n,n whose only in-degrees are a or b. we obtain the main result as follows:Given a positive integer n, let K_n,n be a complete bipartite graph. For a,b ∈{0,1,2,..., n}, [a, b]_n is realizable if and only if there exist positive integers s and t satisfying the following two equations:In Section 1 of Chapter 3, we prove the necessary condition of the conclusion. In Section 2, we prove the sufficient condition of the conclusion, which uses the ideas of the category talk and algorithms.The fourth chapter describes the innovation of this paper, main research conclusion and questions for further research. The innovation of this paper is that the in-degrees of vertices of the orientations are only a or b and the structure of orientations is simple. Later, we may be able to study the orientations of other undirected graph, such as star graph and k—ary n—cubes.