Research On A Class Of Algebraic Bipartite Graphs

In recent years,graphs with high symmetry and large girth have important applications in extremal graph theory,cryptography,coding theory,network communication and quantum computing.In 1995,Lazebnik and Ustimenko first proposed a class of algebraic bipartite graphs D(k,q)with q-regularity,edge-transitive and large girth,which have been widely favored by researchers since its introduction.Furedi et al.proposed a famous conjecture on the girth of bipartite graphs in[7]:for any odd number k and prime power q ? 4,the girth of D(k,q)is equal to k +5.In order to study this conjecture,the auther of[19]demonstrated the equation of the path expression in the bipartite graph as well as proving the correctness of the conjecture when(k + 5)/2 is a power of the characteristic of the finite field Fq by computing the homogeneous polynomial?s(W1,W2,...,Wm),when the vertex chromatic aberration sequence is constant.Then,when the vertex chromatic aberration sequence is an equal-ratio sequence,the auther of[26]computed the homogeneous polynomial ?s(w1,w2,...,wm),the conjecture in the case that(k + 5)/2 is the product of a power of the characteristic of the finite field Fq and the factor of q-1 again to be prove.The calculation of homogeneous polynomial p,(W1,w2,...,Wm)in a more general case is studied by this paper.In addition,we also design the bipartite graphs connected component search algorithm for the isomorphism problem of bipartite graphs D(k,q)and their generalization graphs.In order to further study the conjecture about the bipartite girth D(k,q),this dissertation firstly discusses the computational problem of the homogeneous polynomial ?s(w1,w2,...,wm)with the vertex chromatic aberration sequence like 1,1,a,b,a2,b2,....We first turn this computational problem into a single-parameter variable-coefficient recursive solution problem.To solve the recurrence in a special case,we introduce a new identity(?)by which the formula for the homogeneous polynomial ?s(w1,w2,...,Wm)is given.The auther of[36]generalized bipartite girth D(k,q)and obtained the bipartite graph ?(Ti,q)which has the same number of vertexes and the lower bound of girth with the bipartite graphs D(2i + 3,q).However,it is not clear whether they are isomorphic.For this problem,we propose a bipartite connected component search algorithm by which we calculate the number of connected component of some bipartite graphs ?(Ti,q)and find many cases which bipartite girth ?(Ti,q)and bipartite girth D(2i + 3,q)are not isomorphic.Furthermore,based on the calculation results,we make a conjecture:For positive integer i,k and a prime number p,bipartite graphs ?(Ti,P)and bipartite girth D(2i + 3,p)are not isomorphic when i = 2k.The research on this conjecture will be conducive to the construction of a new infinite family with large girth.