Isomorphism criterion for monomial graphs

Vasyl Dmytrenko, Felix Lazebnik, Raymond Viglione

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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 languageEnglish
Pages (from-to)322-328
Number of pages7
JournalJournal of Graph Theory
Volume48
Issue number4
DOIs
StatePublished - Apr 2005

Keywords

  • Algebraic constructions
  • Graph isomorphism
  • Number of complete bipartite subgraphs

Fingerprint

Dive into the research topics of 'Isomorphism criterion for monomial graphs'. Together they form a unique fingerprint.

Cite this