Two Results On Bipartite Graph

This paper have two chapters, in the first chapter we deal with the problem on minimum diameter orientations of graph G vertex-multiplications(see Definition 1.13). It is the one-way and gossip problems that lead to consinder minimum diameter orientations of graph. Graph theoretical modelling of the one-way street problem can be traced back to the classical paper of Robbins[3]. In [3] Robbins' celebrated one-way street theorem states that a connected graph G has a strong orientation if and only if no edge of G is a brige. For a brigeless connected graph G, let Ω,(G) be the family of strong orientations of G, and for any D∈Ω(G), we denote by d{D)(resp., d(G)) the diamiter of D(resp., G). Define d(G)=min{d(D)|DΩ(G)}. G(s1,S2,...,sn)(this notation comes from [1]) is a G vertex-multiplication for any connected graph G of order n>3 and any sequence (si) with Si≥2, i = 1,2,..., n. Koh and Tay in their paper[1] give a inequality as follows:All graphs of the form G(s1,S2,...,sn) are thus divided into the following three classes: φ = {G(s1,s2 ... sn)\d(G(s1 S2,...,sn)) = d(G) + i}, i = 0,1,2In[l] Koh and Tay also give such a conjecture: if G is a graph such that d(G) > 3 then G(s1, s2,..., sn)∈φ2, Si ≥ 2, (i = l,2,...,n). It is very defficult to give a counterexample or a proof. In this paper we'll verify that it is true for tree(a special type of bipartite graph)vertex-multiplications, and it is a extention to one of the results in paper[l].In the second chapter, from the point of view of non-decreasing degree sequence we give a degree-maximal non-Hamilton simple balanced bipartite graph bm,n. We give a result below. For arbitrary non-Hamilton simple balanced bipartite graph, its non-decreasing degree sequence is majorised~[2] by that of a degree-maximal non-Hamilton simple balanced bipartite graph, i.e, bm,n In this paper, we give the structure of bm,n...