Proof of a conjecture on monomial graphs

Abstract: Let

e

be a positive integer,

p

be an odd prime,

q = p^{e}

, and

B b b F_{q}

be the finite field of

q

elements. Let

f, g i n B b b F_{q} [X, Y]

. The graph

G = G_{q} (f, g)

is a bipartite graph with vertex partitions

P = B b b F_{q}^{3}

and

L = B b b F_{q}^{3}

, and edges defined as follows: a vertex

(p) = (p_{1}, p_{2}, p_{3}) i n P

is adjacent to a vertex

[l] = [l_{1}, l_{2}, l_{3}] i n L

if and only if

p_{2} + l_{2} = f (p_{1}, l_{1})

and

p_{3} + l_{3} = g (p_{1}, l_{1})

. Motivated by some questions in finite geometry and extremal graph theory, Dmytrenko, Lazebnik and Williford conjectured in 2007 that if

f

and

g

are both monomials and

G

has no cycle of length less than eight, then

G

is isomorphic to the graph

G_{q} (X Y, X Y^{2})

. They proved several instances of the conjecture by reducing it to the property of polynomials

A_{k} = X^{k} [(X + 1)^{k} - X^{k}]

and

B_{k} = [(X + 1)^{2 k} - 1] X^{q - 1 - k} - 2 X^{q - 1}

being permutation polynomials of

B b b F_{q}

. In this paper we prove the conjecture by obtaining new results on the polynomials

A_{k}

and

B_{k}

, which are also of interest on their own.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Proof of a conjecture on monomial graphs