Isomorphism criterion for monomial graphs

Let q be a prime power, 𝔽 q be the field of q elements, and k , m be positive integers. A bipartite graph G = G q ( k , m ) is defined as follows. The vertex set of G is a union of two copies P and L of two‐dimensional vector spaces over 𝔽 q , with two vertices ( p 1 , p 2 ) ∈ P and [ l 1 , l 2 ] ∈ L being adjacent if and only if p 2 + l 2 = p l . We prove that graphs G q ( k , m ) and G q ′ ( k ′, m ′) are isomorphic if and only if q = q ′ and {gcd ( k , q − 1), gcd ( m , q − 1)} = {gcd ( k ′, q − 1),gcd ( m ′, q − 1)} as multisets. The proof is based on counting the number of complete bipartite INFgraphs in the graphs.