On recognizing cayley graphs

Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, John M. Robson

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

Given a class C of Cayley graphs, and given an edge-colored graph G of n vertices and m edges, we are interested in the problem of checking whether there exists an isomorphism 0 preserving the colors such that G is isomorphic by 0 toagraph in C colored by the elements of its generating set. In this paper, we give an 0(m log n)-time algorithm to check whether G is color-isomorphic to a Cayley graph, improving a previous 0(n4'752 log n) algorithm. In the case where C is the class of the Cayley graphs defined on Abelian groups, we give an optimal 0(m)-time algorithm. This algorithm can be extended to check color-isomorphism with Cayley graphs on Abelian groups of given rank. Finally, we propose an optimal 0(m)-time algorithm that tests color-isomorphism between two Cayley graphs on Z„, i.e., between two circulant graphs. This latter algorithm is extended to an optimal 0(n)-time algorithm that tests color-isomorphism between two Abelian Cayley graphs of bounded degree.

Original languageEnglish
Pages (from-to)76-87
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1879
Publication statusPublished - 2000

Fingerprint Dive into the research topics of 'On recognizing cayley graphs'. Together they form a unique fingerprint.

  • Cite this