Title of article
On monomial graphs of girth eight
Author/Authors
Vasyl Dmytrenko، نويسنده , , Felix Lazebnik and Dhruv Mubayi، نويسنده , , Jason Williford، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2007
Pages
15
From page
828
To page
842
Abstract
Let e be a positive integer, p be an odd prime, q=pe, and be the finite field of q elements. Let . The graph G=Gq(f2,f3) is a bipartite graph with vertex partitions and , and edges defined as follows: a vertex (p)=(p1,p2,p3) P is adjacent to a vertex [l]=[l1,l2,l3] if and only if Motivated by some questions in finite geometry and extremal graph theory, we ask when G has no cycle of length less than eight, i.e., has girth at least eight. When f2 and f3 are monomials, we call G a monomial graph. We show that for p 5, and e=2a3b, a monomial graph of girth at least eight has to be isomorphic to the graph Gq(xy,xy2), which is an induced subgraph of the classical generalized quadrangle W(q). For all other e, we show that a monomial graph is isomorphic to a graph Gq(xy,xky2k), with 1 k (q−1)/2 and satisfying several other strong conditions. These conditions imply that k=1 for all q 1010. In particular, for a given positive integer k, the graph Gq(xy,xky2k) can be of girth eight only for finitely many odd characteristics p.
Keywords
Monomial graph , Girth eight , cycle , Permutation polynomial , Generalized quadrangle
Journal title
Finite Fields and Their Applications
Serial Year
2007
Journal title
Finite Fields and Their Applications
Record number
701286
Link To Document