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   1 kl   1 m . 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. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 322–328, 2005