• 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