Browse Prior Art Database

Isomorphism of Strongly Regular Graphs

IP.com Disclosure Number: IPCOM000128221D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 16 page(s) / 40K

Publishing Venue

Software Patent Institute

Related People

Richard Cole: AUTHOR [+3]

Abstract

We present isomorphism algorithms for k-strongly regular graphs running faster the larger k. A consequence of our proof is that no "interesting" graph is (d log n)-transitive, for sane constant d. a

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Isomorphism of Strongly Regular Graphs

by Richard Cole

Technical Report No. 63

March 1983

Abstract

We present isomorphism algorithms for k-strongly regular graphs running faster the larger k. A consequence of our proof is that no "interesting" graph is (d log n)-transitive, for sane constant
d. a

1.. Introductio~,

Attempts at general graph isanorphism algorithms often face diffi-culties with strongly regular graphs; for example, Corneil and Gotlieb [3], and Aspvall [1]. Corneil and Gotlieb parameterize the strongly regular graphs as k-strongly regular, k taking integer values. The larger k, the worse their proposed algorithm performs. We obtain iso-morphism algorithms for k-strongly regular graphs running faster, the larger k. This work is of interest too because, by contrast with recent developments in graph isanorphism using group theoretic techniques [5,6,7], we use very simple methods.

We show there is an isomorphism algorithm for k-strongly regular

graphs running in time

(Equation Omitted)

for sane constant c, independent of k and n. In particular, for k=loge, this is a running time of 0(nl gn). Babai [2] gave an isomorphism algorithm for strongly regular graphs run-

ning in time 0(n n1/2 1 gn), for some constant c. However, he did not consider k-strongly regular graphs. In [8] sane isomorphism algorithms for restricted classes of strongly regular graphs are presented; they run in time 0(nclogn), for sane constant c.

In section 2 we give an outline of the algorithm and introduce the concept of a distinguishing set. In section 3 we outline the proof of the running time; details are given in the appendix. And in section 4 we discuss the significance of this work and possible further work.

2.. -The glgorithm

New York University Page 1 Dec 31, 1983

Page 2 of 16

Isomorphism of Strongly Regular Graphs

Definition 1: Let G be a regular graph of degree d8, and let A(vl,v2,...,vr) be the set of vertices adjacent to all of vl,v2,...,vr. G is s, ronaly regular if there exist constants dl,d2 such that

(1)

(Equation Omitted)

, if a and v are adjacent, and

(2)

(Equation Omitted)

, if a and v are non-adjacent.

We also say these graphs are 2. -s.tro.rear. The definition of a k-strongly regular graph is similar: we require, for all h S k, that

(Equation Omitted)

be dependent solely on the isanorphism type of the subgraph of G induced by the vertices

(Equation Omitted)

Clearly, a (k+l)- strongly regular graph is k-strongly regular.

Definition 2,: Let G be a graph. We say G is 2-transitive_if each edge can be mapped to every other edge, and if each non-edge can be mapped to every other non-edge.

The definition extends to k-transitive by requiring a similar pro-perty for each set of hsk vertices: namely, each set of h vertices, which as a subgraph of G induces a graph of a. given isomorphism type, is automorphic to every other set of h vertices inducing the same isomor- phism type....