On the equational graphs over finite fields

Bernard Mans, Min Sha*, Jeffrey Smith, Daniel Sutantyo

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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 Fq of odd characteristic, we define a digraph by choosing the elements in Fq 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)=(Y2−f(X))(λY2−f(X)) with f(X) a polynomial over Fq and λ a non-square element in Fq. We show that if f is a permutation polynomial over Fq, 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.

Original languageEnglish
Article number101667
Number of pages31
JournalFinite Fields and their Applications
Volume64
DOIs
Publication statusPublished - Jun 2020

Keywords

  • Connected component
  • Equational graph
  • Finite field
  • Functional graph
  • Hamiltonian cycle
  • Strong connectedness

Fingerprint Dive into the research topics of 'On the equational graphs over finite fields'. Together they form a unique fingerprint.

  • Projects

    New Applications of Additive Combinatorics in Number Theory and Graph Theory

    Mans, B., Shparlinski, I., MQRES, M. & PhD Contribution (ARC), P. C. (.

    1/01/1431/12/17

    Project: Research

  • Cite this