On the equational graphs over finite fields

In this paper, we generalize the notion of functional graph. Specifically, given an equation $E(X,Y)=0$ with variables X and Y over a finite field ${\mathbb{F}}_q$ of odd characteristic, we define a digraph by choosing the elements in ${\mathbb{F}}_q$ as vertices and drawing an edge from x to y if and only if $E(x,y)=0$. We call this graph as equational graph. In this paper, we study the equational graph when choosing $E(X,Y)=(Y^2-f(X))(\lambda Y^2-f(X))$ with $f(X)$ a polynomial over ${\mathbb{F}}_q$ and λ a non-square element in ${\mathbb{F}}_q$. We show that if f is a permutation polynomial over ${\mathbb{F}}_q$, then every connected component of the graph has a Hamiltonian cycle. Moreover, these Hamiltonian cycles can be used to construct balancing binary sequences. By making computations for permutation polynomials f of low degree, it appears that almost all these graphs are strongly connected, and there are many Hamiltonian cycles in such a graph if it is connected.