Premium
Isomorphism criterion for monomial graphs
Author(s) -
Dmytrenko Vasyl,
Lazebnik Felix,
Viglione Raymond
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20055
Subject(s) - mathematics , combinatorics , bipartite graph , prime power , vertex (graph theory) , isomorphism (crystallography) , discrete mathematics , graph , prime (order theory) , chemistry , crystal structure , crystallography
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