Isomorphism Criterion of Monomial Digraphs over Prime Fields

Abstract

For any Galois field ${\mathbb{F}}_q$ with $q$ elements and any positive integers $m$ and $n$, the directed graph $D(q;m,n)$ has vertex set ${\mathbb{F}}_q\times {\mathbb{F}}_q$, and there is an arc from vertex $(x_1,x_2)$ to vertex $(y_1,y_2)$ if and only if $x_2+y_2=x_1^m{y}_1^n$. It was conjectured in earlier work that two digraphs $D(q;m_1,n_1)$ and $D(q;m_2,n_2)$ are isomorphic if and only if there exists an integer $k$ relatively prime to $q-1$ such that $m_2\equiv k{m}_1$ and $n_2\equiv k{n}_1$, where both congruences are modulo $q-1$. We prove this conjecture over prime fields and construct an infinite family of counterexamples over extension fields.