A Study On A Class Of Algebraic Bipartite Graphs With Large Covers

Algebraic bipartite graph D(k,q) was first proposed by Lazebnik and Ustimenko in 1995, which is q-regular, edge-transitive and of large girth. Due to the large girth which is the length of a shortest cycle of the bipartite graph D(k,q), it has been widely applied in many fields, especially in extremal graph theory, finite geometry, coding theory and cryptography.There is a famous conjecture related to the algebraic bipartite graph D(k,q):Conjecture A:D(k,q) has girth k+5 for all odd k and all q≥4.Conjecture A was shown to be valid when k is odd and (k+5)/2 is a factor of q-1 in [1]. Furthmore, it was proved in [2] that Conjecture A is valid in another special case that (k+5)/2 is a power of the character of the finite field Fq for odd k. We showed in this paper that Conjecture A is valid for some general cases.We mainly generalized the combinatorial numbers in finite field, then gave some important properties of the generalized combinatorial numbers, by which we analyzed Conjecture A further. The paper is arranged as the following:Firstly, we introduced the related definition, background, development and application of the algebraic bipartite graph D(k,q). Secondly, we introduced the construction of a new bipartite graph A(k,q) which is isomorphic to D(k,q) and the explicit expressions of the path in A,(k,q), also introduced the known proof of Conjecture A in a special case. Thirdly, we defined a new combinatorial number θ(k, s), which is a generalization of the combinatorial numbers in finite field, then gave some properties of the generalized combinatorial number, which can be seen as generalizations of the combinatorial equations in finite field, by which we proved that Conjecture A is valid when (k+5) 12 is a product of a factor of q-1 and a power of the character of the finite field Fq.