✦ LIBER ✦

Isomorphism criterion for monomial graphs

✍ Scribed by Vasyl Dmytrenko; Felix Lazebnik; Raymond Viglione

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 88 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20055

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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____l. 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

📜 SIMILAR VOLUMES

P3-isomorphisms for graphs

✍ Aldred, R. E. L.; Ellingham, M. N.; Hemminger, R. L.; Jipsen, P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

The P 3 -graph of a finite simple graph G is the graph whose vertices are the 3-vertex paths of G, with adjacency between two such paths whenever their union is a 4-vertex path or a 3-cycle. In this paper we show that connected finite simple graphs G and H with isomorphic P 3 -graphs are either isom

On Whitney's 2-isomorphism theorem for g

On Whitney's 2-isomorphism theorem for graphs

✍ K. Truemper 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ and __H__ be 2‐connected 2‐isomorphic graphs with __n__ nodes. Whitney's 2‐isomorphism theorem states that __G__ may be transformed to a graph __G__\* isomorphic to __H__ by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitn

A reduction criterion for supereulerian

A reduction criterion for supereulerian graphs

✍ Catlin, Paul A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

Let G be a graph, and let H be a connected subgraph of G. When it is known that the graph G/H (obtained from G by contracting H to a vertex) has a spanning eulerian subgraph, under what conditions can it be inferred that G itself has a spanning eulerian subgraph? 0 1996 John Wiley & Sons, Inc.

The Isomorphism Problem For Directed Pat

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

✍ L. Babel; I.N. Ponomarenko; G. Tinhofer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 237 KB

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path

A Randomized Parallel Algorithm for Plan

A Randomized Parallel Algorithm for Planar Graph Isomorphism

✍ Hillel Gazit; John H Reif 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph Ž Ž 2 . 1 q ⑀ which can be computed by known algorithms in O log n time with

A new planarity criterion for 3-connecte

A new planarity criterion for 3-connected graphs

✍ Alexander K. Kelmans 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 1 views

## Abstract Direct proofs of some planarity criteria are presented.