z-logo
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here