| Abstract: | Let q be a prime power, ??q be the field of q elements, and k, m be positive integers. A bipartite graph G = Gq(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 (p1, p2) ∈ P and l1, l2] ∈ L being adjacent if and only if p2 + l2 = p l . We prove that graphs Gq(k, m) and Gq′(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 |
