Abstract
Let q be a prime power, double-struck F signq 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 double-struck F signq, with two vertices (p1, p2) ∈ P and [l1, l 2] ∈ L being adjacent if and only if p2 + l 2 = p1kl1m 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 subgraphs in the graphs.
Original language | English |
---|---|
Pages (from-to) | 322-328 |
Number of pages | 7 |
Journal | Journal of Graph Theory |
Volume | 48 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2005 |
Keywords
- Algebraic constructions
- Graph isomorphism
- Number of complete bipartite subgraphs