PRACTICAL GRAPH ISOMORPHI SM

Br endan D. McKay
Current address · Computer Science [Link]
Department 01 Comput er SCience Vanderbll t Un1 vers 1 ty
Aust rali an Nation al Univ ersity
Canberra. ACT 0200. [Link] Na shvi 11 e, Tennessee 37235
bdm@::s [Link] au

W e develop a.n improved [Link]'thm for [Link] [Link] a graph

[Link] finding generators for its [Link] grou.p. The emphasis i, on th.e
power of the algorithm fo r ,01 fling pr4ctical problem.t, rather tha.n on the
[Link].l n,iceti u of tJu algo rith.m . Th.e nsult is a.n [Link] [Link]-
011.11. 11I.ccel8/[Link] [Link] many [Link].& with. II. thot/.,[Link] or m ore vertice~, [Link]
i& ver y likely th.e most powerful {[Link]- is omorph-18m progra.m [Link] in use.

INTRODUCTION

In th i s paper we discuss the design of an algorithm for canoni -

cally labelling a ver t ex - coloured graph and fo r finding genera t or s for
its autoao r phism group. Tb is algoritha is a descendan t of one described
in Mc Kay(14 J , which in turn was descended fr om one which first appeared
in McKayI121. Other algorithms which also e mploy some of t he ideas
used by our algortthl'l include those of Mathon !lt}, Arlazarov, Zuev,
Uskov and Farad zev [ 1} and Beyer and Proskurowsk i [2 ]. However , we lLTe
con f ident that our algoritha is sIgnif icantly more power f ul than an y
other publi shed aIEorithm for the practical solution of the isomorphi sm
probl em for gener a l graphs. On t he fe~ occasions where the proof of 4
non- t rivia l assert10n 1s not giVen here, it can be found 1n McKay [15J .

1· 1 Set. and graphs

I n t hIs paper V w111 alWays denote t he set {l,2,···,n}. The

set of all l abel led simpl e graphs with ver tex set lr wi ll be deno ted by
g(V). It G e g(V) and II e V, N(v,G) is t he s et of all eleaents of V
which a re adj a cent to '!I in G. Any othe r graph t heo reti c concep t s not
defined he re can be f ound 1n r4J.

Let X be II set and l e t < be a linear (to tal) order on X.

Suppose Z is a set wbose elements are finite sequences of e l ellents of

Con8ressus Numerant i um, Vol . 30 ( 1981 ) , pp . 45- 87

X (the lenith .ay vary). Then the lezicogrtlphic ordering 0/ Z induced b~

< 1s the linear order < defined as fol l ows. If a=(%t.z~. " ·.Zk)EZ
and {J = (111, 1/:;, ···.11') e Z then a < {3 e1 t her of the follo .... 1ni are true.

(1) For some t, I <t < min{k, l}, .... e have Z; = 1I; for i < t
and %1 < Yt·

(11) %; = 11; for 1 <i< Ie and I > Ie.

If X is a Itnearly ordered set; then .inX denotes the IIlni .um
element of X. In particular, lIine = co. The function max is defined
similarly.

1·2 Partition..

A partition of the set V is a set of disj oint non-eliPty subsets of

V whose union IS V. An ordered pa.rtit1on of V 15 a sequence (VI , V:; • ...• Y.).
such that {VI. V~, ... • Vr} 15 a partition Clf V. The se t of al l partit1 0ns
of V and the set of all orde red parti tions of V will be denoted by
I1(V) and ll(V) respect ively. For notationAl economy we al so define
f1"(V) = f1(V) U mV).

The e lemen ts of a [Link] on (o r ordered partition) 1r E I1"{V)

a re usually called its c~ll •. A trivial cell of 1'1" 15 a cell of cardinality
one j the [Link] of s uch a. cell 15 sa i d to be find by 11". If every ce ll
of 11" is trivial. then 11" is a <[Link] part ition, whtl e i f there is only
one cell, 11" is the [Link] partition.

"/I"~ e IT-(V) , we wr i te 1'1"1 ~ '1'2 i f .... 1 and It~ have the sa.e
If .... "
cells, i n sOlie order. We sa.y that 1I"t 15 finer than "111"11, deno ted 1I" t < 11"2,
i f every cell of 1I" t 1 s a subset of sOlie cell of 11"2' Under the same
c onditions , . 11 is eoa.".!!r t llan .... 1. It is \lell known that the se t n(V)
forms a lattice under the partial orde r <. This . e ans t ha t , given 11"10
11"2 e n(V), there i s a unique coarsest partition 71"1/\ 11"~ e I1(V) SUch that
11"1 > 11"1/\ 11"2 and "/1"2 > . . . 1/\ 11"2. and a unique finest parti tion 11"1 v ""~ e I1{V)
s uc h that "/1"1 < 71"1 V 11'2 and 'lf2 < . . 1 V 71"2_ Each cell of 1I't /\ .... 2 15 a non-
ellPty intersection of a cell of 1'1"1 and a cell of "11"2' Each cell of "11"1 V"ll"~
is a minimal non-empty subset of V which 1s both a Union of cells of
1'1"1 and a union of cells of 71"2'

.
 wll i ch
Let 'If e U-(V) . Tben f1x('If) is the set of ele.e nts of V
are fixed by 11". The &~Pp o rl of 'II'" is Ute set s UP p('II'") =
V \ flx('II'"). The
; I V; E 'II'}.
s e t of minim um. ctll Tl!!pru t nta.ti1l e& of fI' is mcr(1f) = {minY
whe re t he lIinl l1a are under tile na tural orderI ng of V.

1·1 ' L,mma Let '11'1, "11"2 II! n"(V) .

(.) flX(""'1 v.,..., ) = flX(""'l ) n fix(., )

(b) fix{1I"1 /I. '1'1'"2) :> fi X(111) U fix{., )

( 0) SUPP(1f1 \I 1f~) = SUPP('I'I'"l) U SUPP{fr2)

(0) SUPP(1fL11 1f2) C SUPP(1I"1) n SUPP(1I"2)

(,) mer(.1 v 11",) C mcr(1I"1) n Ec r(lr2)

(f) mcr('II'1 /I.. ""'2) = mcr('II'"I) U IIcr(fr2) 0

L" 'If.. " V~) IE il(V). For each %IE V define u(%,,..) = i ,
= (VI, V2,
are cOI'U,'d ent
wllere % IE Y;. If '11'1, 11"2 IE ll(V) then we s a y t hat 11"1 and 11"2
, 1!'2) < U(y,1!'2)'
if, f o r any %, Y IE V, U(t,'I'I'"l ) < u(y,1I"d implie s that U(:t
As a relati on, cons isten c y is s Ylillet r ic but no t trans
iti ve . If 11" 1 < 11"2
-<"'2 or
and '1f t a nd ,.., are consi stent, we indic ate tlli s by writin g 'If.
'lf2 >- ,.. •• The re l ati on -< I s trans iti ve but not s ymme tri c.

1· 4 Group s
eland t
For pe rlluta t ion group t heo ry not del1n eated he re see Wl
S,,). The 1mage
[19]. Le t '1 be a permu tation on V (1n other wo r ds 'T E
y, if W C V
of U E V under '1 1.1 11 1 be deno t ed by 11'1. More ge nerall
', V,) IE g(V).
t hen W" = {'W'J I 'llie W}. Simil arly. if 1f = (V. , V2 , "
t he n 'If'J = (vl , V~, " ' , Vn Finall y, tf G IE g{V) t hen
G" IE Q'(V) ha s
E(G") = {t'Jy'J I 'XII IE E(G)} .
then Q defin es a parti ti on 8(n) E n(V) whose
If Q C 8",
Fo r no tati onal
cell s are the o rbits of (0 ). t he group gene r a ted by Q .
) and .er(a)
conve nience we 1.1111 write B({,}) as 8b), and fix(a) , supp(Q
a nd mcr(8(Q n.
w11 1 be used a s abbre vi a tio ns t or fix(8( n»), s up p(8(Q))
1·3 .
re s pec t ively. The ne xt } " mma follow s ea s ily frOIl Lellllla
'·5 [Link] L flt n, IfJ C Sn. 'J'[Link]

(a) B{O U .,.) = 6(n) v 11("')

(b) flx(n U 4'1) = fh(n) n flx(4J)

(0) supp(O U 4» = supp(a) U supp(tP), .n'

(d ) mer(D U "') C IIcr(O} n mcr(If». 0

Let r<S" and l et n be an y s e t s uch that an a ction of each

'J e r is defined on each element of n. Then the It a.bili8Br of {} in r
Is the group ra = {'1 e r I w'" = w for each IJ e n}. [Link] o f ra are
said to fiz n. The lIIost important cases of this construction are as
follows.

(1) (pf)int~wi.u" stabiliser)

If W C V then Fw = {'1' e r I :1; ' = z; fo r each :I: e W}.

(11 ) (uHJJise stabiliser)

If WCV t hen r{W~ = {1er l w'1 = W}.

(111) ( partition d4biluer)

If n·(V) has cell s Vi, V:/ , ' .. , v;. then r ., = {'1 e r I

'If e
V7 = V. for 1 <i< r} . No te tha t t hi s i s quite dUferent
froll r{:or} = {'1 e r I,..' = 'II"}, unless tI E il(V) .

(1 v) (a.1'tomo rp/lism grClup f)f grllph)

If G e G(V), then the autom [Link] group of G is t he

group Aut(G) = (S,.){e} = {"I E S.. I G1 = G} .

.
DEVELOPMENT OF TH E ALGOR ITHM
In t his section ",e describe the theoretIcal basis f o r t he
a lgor ithm. The aore mundane as pects of i ts impl ementa tio n w11l be treated
1n Secti on 3.

2·1 Canonital Label.

A [Link],l i s a map C: Q'(V) X aWl _ Q( V), such t. hat.

for a ny G E g (V) , 11" E llWl and 7 E S" we have
(C1) 'lG, ffl ~ Q

(C2 ) e(o"', :1("1 ) = 'lQ,"')

(C3) If C(G,ff"1) = C(O,ff) , [Link] :11""1 = 11"' f or MIme 6eAut(G) .
The main use of II. ca no nical l abel is to so lve var ious graph
isomorp his m problems as i ndicated i n t he follo wi ng theore m.

2·2 Theorem L!t G I , O2 E .G'(V) ,:II" E mV) [Link] '7 E Sn. Th~ n C{G 1, 11") =
C(G2, "If'!") i.f and onl y if there -i.J a permutation 6 E S" ,uch that G 2 = G ~ [Link]
1'I" '!" =ff~ .

Proof: The exlstence of 6 as required implies t hat C(G \, 1I") = C(0 2,"II""1) by
Property C2. Suppose c onversely that C(G J ,1I") = C( G ~,1I"1") . By Pr operty C1,
O~ = G~ for s ome fJ e S". Tlle refor e C(G 2 , :11"') = C(G~, 1I"1 ) = C{G 1 ,7I""lr).),
by Property C2. Slnc e C(G J , 1I"} = C(G 2 ,1I""I), the re Is some a e Aut(G I ) such
t ha t 1I""ltr' = 11" <>" , by Proper t y C3, and so 11" ' = ff <>~. But a E Aut.(G I), and.
so O 2 = Gf = G'{~. 0

The isomor ph1 s. probl em desc ri bed i n Theo rem 2·2 can be thought
of as that of t esting ve r tex-col oured graph s f or hoao r phlsl11. Gi ve n 1,..1
col ours, ~e colour the ve r tices of G 1 whi ch 11 e tn "the i-th cell of
ff . . ith the i - th col o ur, t or 1 <i < Iffl. We then $1II11arly col our the
vertices of G 2 i n accorc!.ance .... ith ,..'. This 101111 use the S411e colour s
.... ith the salle fr eque ncy. Theorem 2·2 no~ says that e(G I ,1f) = C(G 2 , 11""1)
if a na only if "there I s II. co l our-preserving i somo r phism from (i J to (i 2.

The most il1portant c ase is, of course, when 11" is t he unit

partition (V), in which cas e Property C3 hold S tr ivially. However we
will l18. i nta i n the more leneral setting we have created , sInce t he added
comp l lclltions .... ill only be slight .

..
2·3 Equitable Partitions

For G E g(V).
V and W C V, we define dG(v, W) to be the
t! E

number of elements of W which are adjacent in G to v. The subscript

G will normally be suppressed. We will say that ,..- e IT-(V) is equitable
(with respect to G) if, for all VI, V 2 e,..- (not necessarily distinct) we
have d(VI, V~) = d{1I2, V2). It is easy to show that the equitable members
of IT{V) form a lattice which is closed under v. Since the discrete
partition is always equitable, it follows that for every 11" E I1(V) there

.,
is a unique coarsest equi table partition E(,..-) E I1(V) which is finer than

One of our first concerns in this section will be to study an

efficient procedure for computing E("'-) from :rr.

2·4 The Refinement Procedure

The algorithm we give here is a descendant of one first described

in McKay [12]. It actually turns out to be a generalization of an algorithm
of Hopcroft ([S), see also [7)) for minimizing the number of states in
a finite automaton, although it was not derived from the latter.

The algorithm accepts a graph G E g(V), an ordered partition

,..- E LI(V) and a sequence a = (Wi, W2, "', WM) of distinct cells of 'IT.
The result is an ordered partition R(G, 'IT, a) U(V). E Under suitable
conditions, to be discussed below, R(G,'IT,a) '" E("'-),

2·5 Algorithm Compute R(G,'IT,a) given q E g(V), 'IT E Il(V) and

a = (WI, W2,"', W M ) C 'IT.

(l) * := 'IT

m:= 1

(2) If (* is discrete or m> M) stop: R(G,'IT, a) = 1i'

W:=Wm

m:=m+l

k: = 1
 {Suppose if = (VI , V2 , ' ", v~) at t his point.}

(3) Define (Xl, X:., ···, X.) IE lI(V... ) such that for any :I: IE Xit
Y IE X j we bave d(~, W) < d(y, W) i f and onl y i f i < j.

If (.! = 1) go t o (4)

Le t t be tbe sma lle st in teae r such t hllt IXII 15 aadaulll

(1::; t < 4).
If (Wj = V... for SOllie j (m <j < M) Wi := XI

Fo r 1::; i <t s e t WM+,:= Xi

Fo r t <i < , set WM+t - 1 := Xi

M:= M+,-l
Update ;r by replac i ng t he cell V... wltb tbe cells X l, X :, ·· ·, X.
in that o rder (in situ.).

(4) k := k + 1

If (k < r) go to (3)

Go to (2) o

2·6 Theorem For Gny G IE g(V), 1T E LI{V), we Mtle R(G,1!', '!!') = €(1T),

Proof: (a) The value of M - m is de c reased In Step (2) a nd is onl y

increased when if is made stri ctly fin er. There fore the algorithm 15
cer tain t o terBinate.

(b) By defi nitio n, €(1T) < 1T, so €('/r) < if at Step (1). No w
suppose tha t e("') < if be f or e s Ollie executi on of Step ( 3). Since W is a
cel l of some partition coarser than €(11') (i e. some earlier value of 1i) ,
it 15 a uni on of cells of €(w). Since €(1T) 15 equitable, we must have
t ba t t(w) <i after the exe cution of Step (3). Therefore, by ind uct i o n,
{ ('If) < R(G, 1I',1!') < 11' .. hen the algorithm stops.

(c) Suppo s e tha t R(G,Tr,Tr) is not equitable. The n for soce YI ,

Y~ e: R{G,1I',1I') there are :t, y e Y1 such thllt d(:Z:' Y2) 01 dry, Y2). Sinc e if

'I
is made successive ly f iner by t be 4lg o rit ~, :t and y must al'oiays be in
the same cell of i-.

(d) At Step (1), Y 2 is contained in some e lement of a. Hence

Y 2 must sOllle t ille be contained in W for a n execut ion a t' Step (3).

(e) Since z and yare never se parated, d(:t, W) = d{y, W}. But
sinc:e W Is a union of cell s of R(G,,..-,l'T) , a nd d(z, Y2) ':1= d(Y,Y2) , there
is at lea st one o the r cell Ys of R(G,1f,If) contained 1n W f or which
d(:r;,Ys) ;;£d(y, Ys). Si nce Y'l and Ys are different cells of R(G,1r,If) t hey
must be separa t ed at some execution of Step (J). At leas t one of theil,
say Y2 will t hen be con t a i ned in s oae new ele_en t of a.

(f) Si nce t he argullent in (e ) can c l early be re peated in-

definitely , the algor1thll ne ver stops, con tradi c ti ng (a) . Therefor e our
assullPtion that R{G, 1t' ,1r) is not equitable must be fa lse , 'o'hic:h pr ove s
t hat R(G,'Ir,1r)~ {('I'I'). 0

An i mpor tan t advantage t ha t Al gorit ha 2·5 has over prev i ous

algor ithms f or computi ng { ('II") is tha t a can s ome tilles be chosen t o be a
proper subset of '11'. One lIethod of choos1ng a is desc r Ibed tn the nelCt
the ores .

2· 7 Theorem Let G E Q(V), 11' e lI(V) and SUppOSIJ that there is some equi.
t abl ~ partitio n fr' which i, coar.!er than 7T. Cho f}u a C '1'1' luch that for any
WE fr', W ~ halJe X C W fo r at mod one X € '1'1' \ a. T hen. ~{ G,1r,a) ~ €"(7T ).

(Il) 8y the s alle argullell t s as i n Theorem 2·6 , t he a l goritha will

eventually stop, am" {(lI') < R(G, 1I',a} < 11'.

(b) Suppose t hat ~(G,1I',a) is not equitable. Then f or some

Yl , Yz €.£(G,1I',1lI) thl!rl! are z, 1jeYI such that d(:t,Y~);;t:.d(y,Yz)' Since
R(G,'I'I',IlI) < 11"', and 1'1" 1s equitable, there 1s at least one oth~r cell
Y3 of ~(G, 11' , Ill) s uch tha t Ii(:!:, Y~);;t:. d(y, Ys ).

Cc) If Y2 and Y 3 are in different cells of .,.., the defined

r elationship be tween 1'1'. a and 'If' ensure s tha t a t l east one of thea, say
Y2 , I s rontal nl'ld In some c e ll of a at Stl'lP (1). We can then t ak:e up the
proo f of Theore. 2·6 a t s t e p Cd ) , and conc lude t hat R(G, 'II' ,a)~{ (.,..).

"
 (d)
On the other hand, Y2 and. Y3 may be in the !lame cell of 11'.
Since they are in different cells of R(G. 1I',c.r) tbey .ust be separa t ed
a t Step (3). At leas t one of t hem, say Y!/., .... 111 then be contained in
some nel>' elellen t of a. We can now take up the proof of Theor em 2·6 at
step (e) and conclude II.S bef ore that R(G,lI',a) ..... e(7I")· 0

One application of Theorem 2·7 occurs when G is regular and "II"

has lIore than one ce ll . The unit part iti on 11"0 is equi table , and so we
can choose a to be 11" l ess anyone cel l. Thts will be part!l;:ularly time -
saving if 11" = (tI, V \ tI) for sOllie tI, In which case we can use a = (tI).

A much 1I0re important app l ication of Theorem 2·7 will be described

in Section 2· 9.

Two ve r y usefu l pro pe r ties o f Algo r ttlut 2·5 are s tated in the
next lemma. Both o f them are i lllmedia te cons eq uence s of the defi ni tion
of the a l gorithm.

2·8 Lemma Let G E Q(V), "II" E n(V). a an o,.dered &[Link] of 1T' and 1 E Sn .
Then

(b) o

2·9 Partition Delb

Let 1T' = (tll ,tl2, .. ·,w.. ) E U(V) and let tI e Vi for sOllie i. I f IVii = I
define "11",>1; = fr. If jv.j > 1 define fT ,,1.1 = (Vi,··· , Yo- I, II, Yo \ 'II, Y.:+I , ··· , Vk)'
Also define 1T' .[Link]= R(G,1T'o>"tI,(tI)).

Given G E .Q(V), If E U (V) and a sequence v = ti l , tilt, ... , tI ... ~l of

distinct elellents of V, we define the partition nut de,.'tl ed /,.om G, 'II"

and v to be [11"1 ,11"2, · ··,11'",1. where

(b ) 11'; = 'll"i_ 1 J.. tI,_1> f or 2 <i< m.

It follows froa Theorems 2·6 and 2·7 that each 'It"i Is equitable.
Define N(V) to be t he se t of all partition nests derived f rom salle
G e Q{ V ), 'It" e U(V) and vector v of distinct elelilen ts of V.
2·10 The basit .earth tree

Q(V) and 11"

Let G E E U(V). Then the s/[Link] tree T(G,1I") 1s the
set of all partition nests 1/ = [11"1,11"2, .. ',71"",] e H(V) such that /I is

derived from G, 11" and a sequence 1Il,tl2,' " ,tI",_1 where, for 1 <i< m~l.

V; 1s an element of the first non-trivial cell of 71"; which has the

smallest size. This definition implies that 11I"il < 111";+1 1 for 1 <i < m.
The elements of T(G,1I") will be referred to as nodes. The
length 1/11 of a node 1/ is the number of partit10ns it contains. If
/I= 111"1,11"2, .. " 71"",1 is a node then 1.'(.) denotes the node [11"1,11"2, .. " 1I"i), for
1 <i< m. Thus 1.'("') = /I. If m > 2 then v Is called a [Link] of
/I(m - I). Similarly, /I 1s a descendant of 1.'(') (and /I(i) is an [Link]
of v) if 1 <i <
m. The root node [11"1) 1s an ancestor of every node
other than itself. The set of all nodes equal to or descended from a
node 1/ [Link] the s1/,btree of T(G,1T) rooted at v, and is denoted
by T(G,'I'I",/I).
If the last partition in a node is discrete, /I will be
called a terminal node.

Suppose that VI and /12 are distinct nodes, neither of which Is a

descendant of the other. Then for some i. /I~;) = v~;) but V~'+lJ =F vh·+ 1 ).
The node 1.'\.+1) wl1l be denoted by 1/1~/l2 and I/~"+I) by /l2~/ll'

The natural linear ordering of V can be used to provide an

ordering < of the nodes of T(G,fI"). Let VI and /12 be distinct nodes. If
/11 Is an ancestor of 1-'2 then /II < /12' If neither of /11 or 1/2 1s an ancestor
of the other, there Is a node [1"1"1,11"2, •• ·,11"",1 and vertices Vl =F 112 such
that /11 ~ /12 = ['1'1"1, '1'1"2, .. " '1'1" tn, ff m .1. till and 1.'2 ~ /II = [fft, ff2, .. ',11",.", 11"", .1. 1121·

Then we have VI < 1.'2 if VI < V2' If VI < /12, we say that VI is earlier
than 1.'2. and tha t /12 is later than VI'

Some of the obvious properties of this ordering of T(G,1I") are

listed in the next lemma.

2·11 Lemma Let G E Q(V), 7r E II(V) and /11, /12, V3 E T(G, 71"). Then

(a) Exactly one of VI < 1.'2, 1.'1 = /12 and /12 < /II is tru.e.

"
 (c) If 111 < 112,
11'1 E T(G,'II", 111) and V:/. E T(G,'II", 1I2) then 11'1 < 1I~,
except pO$.tibly if 111 i.t an. [Link]&tor of 112.

Given G E -'!(V) and. 'II" E a(V) we can gene rate the e lellents of
T(G,fI') In the order given by <, with the simple backtrack [Link].
gIven bel ow.

2· 12 All'Orithm Gllmerate T(G, 11') in th e order eariie8t to lat ed , given

G E M(V) and'll" E mY).

(1 ) It; := 1

'11'1: = .R.(G,1I','If)

(2) If (1I't Is dis c rete) go t o ( 4)

w,.:= fir s t non-trivial cell at '11'1; ot tbe smallest size.

(J) If (W" = 0) go to (4)

v: = mIn W~

Ie:= k+ 1

Go t o COl}

(4) Ie := It; - 1

If (k > 1) 110 to (3 )

Stop: All tbe nodes of T(G,'Ir) hIlve been out put in tbe
required order. o

"
2·13 Group Action. Oil T(G ,~)

If II " ',1I"",J E f:!(V) and '1 e 5.. , then we can define

= [1rl,1T2 ,
,,"I = ['lrI,1fl,' ", ";:'J. Obvious ly II" E li(V). The property of Alaorlthlll
2·5 descr i bed in Lemma. 2·S ha s imlledi ate consequences f or T(G,'II'" }, IS we
describe in the next t heorem.

2·H Theorem Let G e G(V), 'Ir e mV) 4nd'J E Sn.

(a) T(G"I ,rr"l) = T(G,'II'")'I .

(b) If II e T(G, 1I"), [Link] T( G'"', ", .. , ,,"I) = T(G, 11", "p. o
The map fr om T(G, '!f) t o T(G,"p I nducect by '1 w11 1 not tn general
preserve the o rder1na <.
We wl11 be pa rticularly intere sted in pe rmutations 'J E Sn such
that G" = G and ","I e '!f. I n other word s, '1 e Aut (G)" . If "I> II:.! e T(G,1I')
a nd II::: = "I for sOllie '1 E Aut {G) .. we write V I '"" V::: and sa y that " 1 and
II::: are equivalent. By theorem 2·14, ...... is an equi valence relati on on
T(G,1f). If v is a terai nal node of T(G,'!f) t he n v is ca ll ed a n i [Link]
nods if the r e is no earli er node of T(G,:rr) wh ich is equi valent to v.

The foll owing t heore. 1s fundamenta l to our treatment of group

actlons on T(G, w).

2·15 Theorem Let G <I!! .Q(V}, 11" e LI(V) 4nd'1 E Aut(G)" . [Link]

(a) T(G, '!f)" = T(G, '!f).

(b ) IfveT(G ,w), tlu n T(G,1!',") = T(G, 'Ir, IIP.

(c) If VI, v::: E T(G , '11'), VI < 112 Gnd lit ' " v:::, t hen T(G, '11', V2 - VI)

contain& no identitll nod ~, .

Prool : Asser tlons Ca.) and (b) are [Link] e conseque nces of Theorell
2·14, so we conSider on ly a.s serti on (c) . If Vi ....... 112, there 1s SOlie
'1 E Aut( G) ~ = Vf ' But then
such tha t "2 V::: - V I = (YI - 112P [Link]
so T(G,'Ir,V2 - "'I )= T(G,'II", VI - " 2P by (b ) . Ho wever VI <~ and sO
"' I - v::: < 112 - Vi> by Lemma 2·11. Ther efore, e ve ry ter1llinal nm1e i n
T(G, '!f, V2 - VI) is eq ul valent t o an ear li er termInal noDe i n T(G ,:If, "' I-II:::).
whi ch proves (c:) .

"
2· 16 Indicator rund ionl

Let .1 be any 1 t nearly ordered set. An indicat or function 1s a

lIap A :g(V)XlJ{V)[Link](V)-> .1 such that A{G",1I"' ,v') = A(G,'II",v) for
any G E Q(V). 'II" E mY), v e T(G,'II") and..., E Sn·

Given one indica tor function A, we can define ano the r ind icator
function ,1 by

where k = Ivl. wi t h t he l exicographic ordering Ind uced frolll the ordering

of .:1 .

2·17 Definition of C(G,"!!)

If v = ['11"1,11":1, " ','11"",] Is a te rminal node of T(G,'II") t hen'll"",

1s a discrete ordered partition, by definition. This .eans that 11" ....

defines a.n ordering of the decents of V. We can define a graph G(v)

[Link] phic t o G by relabelling the vert i ces of G in the order tha t
they appea r in 11" .... More pr ecisely, If " .. = (til I"~ I··· 1tin), and 6 E S"
Is the perllutation taUng V; onto i for 1 < i:5 n, t hen G(v) = d. The
followin g leMma is an lIlllediate consequence of the defin itions.

2·18 Lemma If G E s:i(V), 'II" E II(V), ..., E Sn and II E T(G,1T) is a. terminal

[Link], then G(II') = G( II) if an.d only if1 E Aut(G).

Proof: Let v = [11"1 ,'11"2, · ··. '11"...1, where '11' ... = (VI [ \/2 1··· I V.. ), a nd take
the pe rauta tio n 6 E S .. whic h takes 11; onto i for 1 < i < n). Then
G(v) = d by def i nition. Also by definition, '11";' = (,,11111 1'" I ,, ~),
snd so G(v') = G"'- II. Thereto r e G(v) = G(v') if and onl y if G' = G"'- 'I,
which is possibl e 1r and onl y if 1 E Aut(G). o
Our next requir ement Is a linear ordering of Q(V). Any such
onler ing will do, but it will be convenie nt f or us to use an ordering
defined using the adja cency aatrices of elements ot Q(V). GIven G E Q(V)
we can define an integer n.(G) by writing down the e i eCients of the
adjacency aatrlx In a r ow- by- r ow fash ion, and interpr eting the result as
an n 2 _bit binary number. If Glf G 2 E Q(V) we can then define G l < G2
if and only i f n(G l ) < n(G2).
We can at last define C(G,'Ir). Let X(G,'Ir) be the set of all
terminal nodes of T(G,'II"). Choose an arbitrary (but fixed) indicator
function A. Let A* = max{.1{G,7r,v) I v E X(G,'II")}. Then we def i ne
C(G,w) = max{ G(II) III E X(G,7f) and AlG, 1f, v) = A*}.

2·19 Theorem C is a. .[Link].

Proof: We show that C has Properties Ci~ C3 (Section 2·1). Property

C1 is true because G(v) '" G for any v E X(G,7f). Now let 'Y e Sn. By
Theorem 2·14, T(G"', '11"1") = T(G,1f)'!" and so X{G1','II"1') = K(G,1r)1". Also,
by the definition of indicator function, &01",7f1',v1') = M:G,'II",v) for
any v e X(G,7r). Finally, by the definition of G(v), we find that
G"'(v1") = GCv). Therefore C has Property C2.

In order to prove Property C3 we must recall Lemma 2·8 (a).

Together with the fact that any v e X(G,'II") Is a parti tion nest, this
implies that C(G,1f) = G 6 for some 6 E Sn such that 7r i = '11".

Now suppose that C(G, '11"1") = C(G,'II") for some 'Y e Sn. Since C
satisfies Property C2, C(G,1l"1') =
-,
C(G"' ,1f}.Therefore there are a,
I
(j E Sn such that 1f0" = 'lr P = '11", C(G,1r1") = G1'- O and C(G,'Ir) = GP. The
assumption that C(G, "1'1"1") = C(G,1r) thus implies that G1"- O = G~ and so
I

(ja-1'Y E Aut(G). Finally, 7f~o-l1" = '11"1" since 1ffJ = '11"'" ="1'1". Therefore C
has Property CJ. 0

An elementa ry means of computing C{G,1r) is now apparent. Using

Algorithm 2·12 we can generate every element of K(G, "1'1"). We can then
identify those II e X(G,"I'I") for which MG,1f,v) is maximum and so find
C(G,'II") from its definition. It is not necessary to s t ore all of K(G,1f)
slmul taneously; its elements can be processed a s they are generated and
then dIscarded. However, this process IS not practical for use with
a great many graphs because of the size of K(G,7r). One problem is
with graphs having large automorphism groups. Since Aut(G) acts seml-
regularly on X{G,1f), IX(G,'Ir)1 must be a multiple of Aut(G), and so can
be impossibly large, even for moderate n. Secondly, there are graphs

"
fo r which IX(G,"-)! i s very larae, even i f IAut(G)1 is small. We w11l
lIeet some of t hese grapbs in §3.

The metho~ which we will use to attack these difficulties I s a

process of pruning T(G,"'-). Let us say t hat II e X(G,1I') is a canonical
node i f C(G, 11') = G(II). Obvi('lusly, any part of T(G,1I') can be ignored U'
the remainder is known to contain a canonical node. OUf guiding 11ght
1s the following thee r ell, which is already implicit in the foregoing.

2·20 Theorem Let G E Q(V}, LI(Y), and A"' = ux {A(G,1r,II) 1 11 e

11" E:

X(G,,..)}. LetX"(G,1f) be any ,ub,et o[ X(G,w) which [Link] thole identity

node.; II for which ltiG, 'If , £I) = iO. Then X·{G, w) [Link] a. canonical node.
D

In the te rms of Theorem 2·20 our aim will be to reduce the size
of X*(G,lT) as lIuch as possible. We will reduce the nUliber of el e ment s
Of X*(G,'!I') which are not identity nodes by searening for autollorptlisms
of G and ellploying any we find te delete subt r ees of T{G,1f). We will
reduce the number of Ideotl t y nodes In X"'(G,1f) by using A.

2·21 Vaing automorphilml to pt'une T(G,'If)

The existence of one or more automorph:lns of G can be inferred

during the gene r ati on of T(G,1I') in at lea st two dUfe rent ways.

(1) We lIay find two t erminal nodes Ill' £I~ E X(G, '11") such that
G(v,) = G(",).

(2) We CAn sOlletlmes infer the presence o f auto~or pbl slls fr om

the structure of an equitable partition.

The first case is tbe more important and will be treated first.
The second case can vait until Section 2·24.

Suppose then that during the generation of T(G,1I') we encounter

a terminal node £I~ E X(G, '!I'). compute G(£I~), and discove r that i t is the
same as G{1I1) for sOlie earlier terminal node £11' Since III and II~ Are
teninal nodes, ther e Is a unique penutation '1 E SOl such that £12 = 111.
It then follows from Lemma 2·18 that '1 E Aut(G). We will call 1 an
e%piicit au tollo rph l s ll.

"
 Once we have found an explicit automorphism there are several
ways we can put it to work. These are based on Theorem 2·15. The immediate
outcome of Theorem 2·15 is that we may ignore the remainder of the subtree
T(G,1I",V~-Vl)' However, we can do better than that. Since Aut(G) is a
group, not only '"/ but all its powers are in Aut(G). Moreover, if we have
found several automorphisms of G, any permutation which 1s generated
by these is also in Aut(G). The follow1ng scheme for handling this mass
of information 1s not always the best, but has been found to work very
well in many circumstances.

Let r E X(G,1f) be the earliest terminal node. We w11l need the

following lemma.

2·22 Lemma Let VI < V2 E X(G, 11"). Then I~ - v21 < IVI- v~l.

Proof: If 1£11 - v21 < It - v21, then V2 E T(G, 1r, r - VI), whi ch contradicts
the assumption that III < v~. o
We next introduce an auxiliary partition fJ E n(V). We initially
set 9 equal to the discrete partition of V, and whenever we obtain an
explicit automorphism 1, we update 9:= 9 v 9(1). This means, by Lemma
1·i3, that 9 is at every stage the orbit partition of the group generated
by all the explicit automorphisms so far discovered. It also means that
9 <9(Aut(G)"-m)' where [11"1,11"2," ·,11"...1 is any common ancestor of all the
terminal nodes we have yet considered. This is because a permutation
taking one node to another fixes their common ancestors.

Now consider a node v = [11"1,11"2, "',1I'm1 which 1s an ancestor of r.

Because of the defini tion of t, v is also an ancestor of all the terminal
nodes generated so far. Let W = {\ll,\l2," ',IJIo} be the first non-trivial
cell of smallest size of 11""" where IJI < 1J2 < .. < 1J1o' Since 9 <1I'm, (J

induces a partition of W. Now the successors of v, in the order earliest

to latest, are V(\ll), V(1J2),' ", V(VIo). where V(Vi) = [7fl' 11"2, "', lI'm, 11'", .1. Vi1.
If '!Ii < IJj are in the same cell of (J, there 1s some automorphism 1,
,generated by the explicit automorphisms so far discovered, such that
lI(tlj) = v(v;p. Therefore we can exclude the subtree T(G,1I',v(\l JD from
further examination. There are two ways of doing this. The first 1s
that, as we generate successive subtrees T(G,1I",V(IJI)), T(G,1r,V(tl2))'

..
 we only consider those for which 11; e mcr(6). The second Is that,
upon discovering an explicit automorphism 7 during the generation of
T(G,1I",V('!Ii)), and updating 6, we check to see if it still true that
v; e IIlcr(6). If no t , we have found proof (namely 1 ) that T(G,1I",V(lIi))
only contains terminal nodes equivalent to those of some subtree we have
al teady examined. Therefore we can return at once to v and consider
V(VH I)'

The technique just described often allows us to jump all the

way bac\::: to an ancesto r v of ~ after only generating one terminal node of
a subtree rooted at a successor of v. Unfortunately this is not always
possible, for example when a new terminal node is not recog nised as
being equivalent to an ea rlier one. It will also be possible (due to the
use of A - see later) for a whole subtree to be ignored without knowing
it to be equivalent to anything else. In order to put our automorphisms
to work in such cases we have devised the following scheme.

Firstly, we maintain a store 1If which contains (flx{1), mcr(1))

for every explicit automorphism 7 so far discovered (or some subset of
them). Tben, with each non-terminal node v e T(G, 11") we associate a set
W(v) C V. The first time (1f any) we encounter v in the search of
T(G,1I"), W(v) is set equal to the first smallest non-trivial cell of
11""" where v = 111"1, 1r2 , ... , ff m ). The next time we encounter v (if any), we

redefine W(v):= W(v) n mCr(71) n mCr(72) n· .. n mcr(7r), where 71,72, ... , 1r

are those previously encountered explicit automorphisms which fix v.
From then on we can ignore subtrees T(G,ff, V(V)) for which tI t: W(v). This
is justified by Le mma 1·5. The reasons for deferring the modification of
W(v) until the second encounte r with v are (1) that the subtree rooted
at the earliest successor of v has to be examined anyway (since the
smallest element of W(v) before the modification remains 1n W(II) after
the mod ification) and (i1) that there is often no second encounter w.1th
v (we may find an automorphism allowing us to jump bac\( to an ancestor
of v). The next lemma shows that we can determine whether 1 fixes v by
100k1ng at fixf1).

2· 23 Lemma Let 7 be an explicit automorphism. Let v = [11"1,11"2, .. . , ffmJ e

T{ G, 11") be deriv ed from G, 11" and VI, V2, ... , V.... _I . Then 1 fixes v if and only
if {tll,1I2' ·· ·, 1Im_l} C flx(1) . 0

61
 There is one other circumstance under which we may wish to
change W(II).If we find two equivalent terminal nodes Ill! 112 where
112 = 111 and where II is the l onge s "!: common ancestor of V l and 112. we can

set W(II):= W(II) n mcr«r).

2·24 Implicit AutomorphisIDs

There are occasions when we can infer the presence of one or

more automorphisms without generating any of them explicitly. These are
based on the following lemma.

2·25 Lemma L et G I: .G(V) [Link] let 'II" E U(V) be [Link] with respect to
+
G. If 11" has m non-trivial cells and either n < IlTl 4, n = 111") m or +
n = )lTl + m + 1, then IT1 = 8(Aut(G).,,) for [Link] equitable 'lT1 < 11". 0

The most commonly occurring case of Lemma 2·25 is when n= i'IT! + m,

which corresponds to 11"1 only having cells of size one or two.

Lemma 2·25 can be put to several us es. The most immediate

application is that whenever we encounter a node v = [11"1,'11"2, . ",'lTmi for
Which 'IT.". satisfies t he requirements of Lemma 2·25, we can infer that
all the terminal nodes descended from II are equivalent, and so at most
one of them is an identi t y node (the earliest one, i f any). A less
direct technique is to store the pair (fix(1I"m), mcr(lT m)) in the list
11', along with the along with the similar pairs derived from explicit
automorphisms. I t can then become useful in pruning later parts of the
search tree.

2·26 Eliminating identity nodes

The technique s of the last few sections are generally quite

efficient in removing terminal nodes which are not identity nodes.
However, t here are occasions when the number of identity nodes is
unmanageably large. Examples of these will be given in later sections.
"Some of these can be elimi nated by means of an indicator function A.

Suppose that during the s earch of T(G,1I") we maintain a node

variable p. When the first t erminal node! is generated, we initialise

61
p := !. Thereafter we update p:= v whenever we find a termInal node ",
>
4,{G, 1I',p} or d(G,.,V}= d(G , ., p} and G(v} > G(p}.
s uc h that iYG,. , ,,,}
Tbe definition of C(G,"') ensures that by the ti.e we have finished
searching T(G,:pr) we have G(p) = C(G,1I'), provided the set of terlllinal
nodes examined includes a ll the identity nodes. Now suppose that at sOlDe
i nstant during our search we have p = [11'1, 11'~, .. " '11" ... 1 and encolUlter a nod!!
v = [."r1,1I"'2t .. ·. 11"'/01, not necessarily terminal. Le t r = lIIin{m, k}. Then,
i t 4{G,1I",v(r)) < MG.1f,p(r) , ·th!! definition o t an indicator functi on
t ells us th4 t .[Link],1I", v) < d/..G, ff, p) f o r every [Link] node II o f T(G, rr).
Tberefor!! w!! can ute ly i gnore T(G,1I",v) wi t hou t .l sca l c ulating C(G,.).

The efficiency ot th is techniq ue d!!pendS .ainly on two fa cto r s .

On Is the powe r of tt in distinguishing h!!tw!!en non-equival!!nt nod!!s.
Tbis, of course, can only be improved by changing A, which wIll g!!n!!rally
involve a power/comput a t ion- tilDe trade-off. The other factor depends nn
the initial labelling of G. Suppose that we wish t o s earch the subtr!!es
T(G,1I",vd . ···, T{G, "II" ,v.). Where V1,V2, ···,v. Ilre the successors of v, in
the order ea r li e s t to la.t e st. We can use t he 1nfor ma tion provided by
A by ignoring the s u btre!! T(G, "Ir , Vi) if A(G,1I",,,,.) < A(G,. , v;) f or so.e
j < i. The n umber of subtree s whicb are t hus Igno r ed could vary from none
( 1f the A(G,"II", Vi) ar e 1n nOn-dec reasi ng order), to t h!! maxlmull numbe r
poss ible A(G,1f,v.) < A(G,1I","'l) for 1 <,;:::; r l . While the.r!! 1s no
(if
efficient wa.y of ensuring that the best case always occurs we can arrang e
for the worst case to be very un lik!!ly. The s imple s t way of doing thts
{but not the on!! we will adopt ) 1s to label G 1n a r a ndoll fashion before
co_enc1ng the generation of T(G,1I"). A p reeise statistic al andysi s of
how tills !!ffects the overall effic i ency wo ul d he ve ry difficult, but
a rough i d ea can perhaps be gained fr om t be f oll owing t wo the ore.s.
We will use E (X) t o deno t e t he exp!!ctation of a rand oll variable X.
The fIrst theo r em s ugg!! s t ! tha t the nUllber of ignor ed sub tr e es wI ll not
usually be much 1!!S! than the maxlllull nUllber poss \. bl!! .

2·27 Theorem Let 61 < 62 < ... < 5" be eiementl of a. [Link] ordered ut
£!,. Let ml, m2, "', m", bt pOlititl e int eger', and p~t I = ml + + ... +
m2 m~ .

L et :tI t :t2, "', :tl b! t lemtnh rJ/ .6, t:tactiy mj of which. au !qual to 5j for
1 < j < k . N ow permuh the :ti at random to get :ttl ), 2;(2), •.• , :r;£'), each. 0/

th e I ! possible permutation.. bei719 equally lihly. F or 1 <i < I, ~ x(· ) 11

63
:t(il > ::c(il for i < i, out ::c(i) "'" 6" . Let M oe tht ,,"umoer ojmarkrrt eltmt""t.s.
Then

where the IUm il ~aA: en 41 0 if k = 1.

In particular, if mj = m j ar 1 <i< Ie, tlun

.-,
E(M) ~ " . m < ' 0'(''),
~Jm+l
1-' o
The second theorell concerns the nUllber of va lues of 4{G,1I",tli)
for those T(G,1I",v;) which a r e not ignored. I t therefo r e hIlS a bearing
on the number of ident ity nodes which are excluded by means of A.

2·28 Theorem Under th.e conditions of T heortm sun, let N bt tlu n"mbltr
of differtm tll1luet amonglt tM marktd dementi. Then

< log I,
+m" -
'Where th.e .urn il 0 if A: = 1. In particular, if mo· = m for 1 <i< k. then
E(N) = E;_:fl < log ic . 0

An alternative to this technique for using A Is to cOIiPute

A(G,'II",II") for 1 <i< \" and then only search T(G,'II",lIi) for those II; for
which ~G,,,.,1o';) is t he largest. Thts 1s undoubtedly the best approach In
III1ny cases. However we are not adopting t his Ilet hod beca use it severely
degrades the a verage-case behaviour. This is because t he discovery of
automo r phislls frequent ly a ll ows us to reject a subtree T (G,'If , 1o") without
ever co_puting v;.

The theo rems above re l a te to the ef f ect of performing an 1nitlal

ra ndom relabel l ing of G. The r easons we are not adopting t his ap proach
are, fir st l y, that tbi s relabelling aay almost double the total execution
U_e (tor a ve r y large randoll graph; see Section 3·10) an~ . $e4;ondl y.
tha t In order to make $ome of the output useful (e. g. the list of

..
au t ollorpbi slis produced) it may be necessary t o translate it back to
the o ri gina l l abell ing, whic h is inconven i ent. "'e wH l describe an
alternative , but ..,111 onl y jus t 1fy it qualitatively. A more precise
ana lysI s woul d be impOSS i bly di f ficult to perform.

Let A' : Q'( Y ) X my) x N(V) -.. .1 be any conven i e nt indicato r

f unc tion. Now de vise It lIIa p / : .1 ..... 11 wi th t he pro pe r ty tha t fo r pairs
:1:, y e ..:1 , z - y is very poorly cor r elat ed ""ith /(: ) - /(y). (This is
no t mea nt to be a r i g o r ous Ijefini tlon). For example , t ake ..:1 = [-l.l[
and /(2;) = sin(lOIOz); the sign of :t - y is very poor ly correla t ed
with tha t of f(:::)- f(y). Now defi ne A by A(G,'II".II) = t( A'(G,'II',v» . The
hope I s t hat any tendency t o an unfavourable o rde r ing of t he values
of A'(G, lr, vl).···, A'(G,[Link]) will not occur fo r A(G,lI",III),···, A(G,lI".lIr).
Howeve r, as we have stated, the r e Is lit t le hope ot an exact sta t is t ical
analysis. The best .... e can say i s that t he computational e xperience is
favourab le.

2·29 [Link] of identit y node.

Up to this poi nt we have been t/lc itly auuming t hat we are

keeping a rec ord of all those identity nodes so far gene ra ted, so tha t
we ca n r ecognize la t er [Link] nodes which are equivalent to a ny of
t hem. In pra c t ice this can cause a s eve r e storage problem, since t he
numbe r of identity nodes can be ve ry large, even if we do n't count t hose
.... hi c h a re eli minated by use of a n indicator function . The r efor e i t is
necessa ry to put a limit on the [Link] of ide ntity noljes (s trictly,
termi nal nodes not known t o be equ i valent t o an earlier node) to be
stored. The OpU .UIl s t rateiY is no t c l ear. On the one ha nd, stor i ng
.ore Identi ty nodes illproves our c hances of detecting autollorph i sms,
'll"hlch can be pu t t o use a s we have seen. On t he other hand, tes t ing t'll"O
[Link] nodes f or equivalence is quite time consuming (espe ci ally for
large graphs) , and ha ving to do a l ot of these tests would have a very
bad e f fe ct on t he overall execut ion time.

The technique which we have adopted, wi thout a g r eat deal of

t heoretica l justificatI on, is to store two ident i ty nodes at a time .
The earl i est terllinal node t 1s a l ways stored. The other termi nal node
(which cay be the same as t he f ir s t ) Is our best guess so far at the

"
Identi ty node [Link] to C{G, 'If). This 15 the node p referred to
1n Sl!ction 2·25. WI! a1 so pl!rmi t thl! &1gor1 thlt to sl!arch for terllina1
nodes equivalent to r, with t he [Link] of using the automorphislls thus
d Iscovered to shorten the total amount of work:. This will s OlleU_es
degrade the perforllanee somewhat, but on the aVl!rage it works vl!ry well.

We are now able to [Link] the way in wh ich terminal nodes are
processed. Suppose that ."e have Just created a node v , not necessarily
terminal, which is not an ancestor of , (1. e. I S later than O.
The node p and the partition 8 have tbe. saae i nt e r pretation as
before. Suppose that II 1s the node [tr l ,'lr2' ·· ·,'lrk] so that 1111 = k. Also
define m = Irl and r = Ipl, and define variables as foll ows.
kh: I f.,..." satisfies the requirellents of Lelllla 2·2 5, then hh is
the silalle st value of i, 15 i < k, for which 'Ir; satisfies
these r equi re ments.

Otherw1 S6 , hh = k.

ht: Tbis 1s tbe SlI4llest value of i, 1 <i < m, f o r whicb

all the ter minal node s descended froll or equal to ,til have
been shown to be equivalent.

h: The longest COllllon a ncestor of , and II 15 lI(h l.

hb: The longest [Link] ance sto r of p and v is v (.\&).

hzb: This is the lIaxhum value "Of 1, 1 <i< min{k, r}, such
that .:UG,1r,,,(i») = MG,'Ir,p{;~.

By returning to 11(;) we !IIean backtracking in the searcb t ree to

IPl and proceeding IIi th t he next successor of v(;) not ye t generated, if
any. If t here ar e no such successors, we return to lI(i-l}, /lnd so forth.
Return to vIOl 1s equivalent to stop.

Now suppose we have Just created v = V(k). Let ~= MG,"",").

(1) If (k >
m or A =I- 4(G,""' ,,( ~1 and (k > r or
A< .d(G,.".,p{kl»)) go to (8) .

..
 (2) If v is non-terminal, proceed to search T(G, 11", v).

(3) If (k> m or A~A(G,1I",.I") go to (4).

If the permutation, taking t onto v is an automorphism,

go to (A).

(4) If (k > r or A< ll:(G,1I",p) or (A='&G,1I",p) and

G(v) < G(p))) go to (B).

If (d>4(G,1r,p) or (A=d(G,1I",p) and G(v»G(p))) set

p:= v then go to (B).

If (d= 4{G,1r,p) and G{v) = G(p)) let, be the permutation

taking p onto v and go to (A).

(A) {At thls stage ;"e have found an automorphism ,.}

(Al) Add (fix(,), mere,)) to 1/1" (1f there is room) and set
6:=6v6(1).

(A2) If (v E mcr(6)) return to v(l». Otherwise, return to

v(Io~).

(B) {At thi -s -stage we have a terminal node v not known to be

equivalent to an earlier terminal node.}

(Bl) If (hI!. < k) add (fix{1rhh), mcr(1rhh)) to 1/1" (if there

is room).

(E2) Return to v(;), where i=min{hh-l,max{ht-l,hzb}}.

The only feature in the foregoing informal algorithm which we

have not already justified is the use of the variable ht in Step B2.
What we want to do in Step B2 is to return to the longest ancestor
V(i) of v which may conceivably have a terminal descendant which is
either equivalent to S or improves on p as "the best canonical label so
far~. All the terminal nodes in T(G,1r , V(hlo») are known to be equivalent
to v, so we can assume that i < 11.11.. FUrthermore, if i> hzb, none
of the descendants of v(i) can improve on p. Finally, if i > kt, and
one of the descendants of v(i) was equivalent to l then v(;) would be
equivalent to .1"(;)' However, all the terminal nodes descended from .I"(i)

67
are equivalent, and so all those descended from V<" are equivale n t,
giving a contradiction.

2·30 We will now give a forl&&l description of the cOlllplete alg orithm.

N()tu: (1) lab and cAg are boo lean var i ables. If lah = [Link], p 15 not
used, and the algori th. only searches for terll1inal nodes equivalent to
~. We will s how I n Theo rem 2·33 that use tul into rmation a bout Aut(G) 15
still obtained.. If dig = true, the algorithm will not use Lemma 2·2 5,
and. will be vaUd f or digraphs and graphs with loops (for which Lemma
2·25 does not ho l d) .

(11) The va riable J.I r e fers everywhe r e to the node [71"1,71"2, ···, 7I"~1.

It t bus change s val ue i f 11"; (l <i < k ) o r k changes va lue.

(111 ) L >1 is an integer specifying a limit on the number of

pairs (f1X(2:), .cr(2:)) t o be stored at ti~e. The result computed by the
algo rl t b. Is independen t of t he cholce of L, although the eff iciency
In general may not be .

(1 v) P C;;;; il(V) is the set of all ordered pa r ti t i ons of V

which satisfy the require.e nts of Lellma 2·25.

(v) We are [Link] f or convenience tllat A(G,1I",J.I) is real 1n

val ~ . I f this 15 not t he case replll ce "qzb:= A.I" - z b,,n by

_', 1f [Link] < "b/o

qzb:=
{" 0, if AJ. = zbk
1 f A.I; > zb"

2·3 1 Algorithm GilJ ~n G E g(V) and 7r E a{V), find g~n~[Link] for Au t(G),.
and (optionally) compu.t~ C{G,7r) .

0) k := Jize := 1

h := lub := indez := I := 0

8 := discrete partitio n o f V

kh:= 2

"
 I f (1fl E P and dig = false) hk:= 1

If (1f1 is discrete) go to (18)

W1 := first small e st cell of 11"1

Vt := minWI

(2) k:= Ie + 1

Ai<:= A(G,1f,II)
If (h= 0) go to (5)

If (hz! = k -1 and A;, = z/k) hz!:= k

If (lab = !alae) go to (3)

qzb := A.;, - zb k

If (hzb = k-l and qzb = 0) hzb:= k

If (qzb > 0) zb k := A.;,

(3) If (hzb = k or (lab = true and qzb > 0)) go to (4)

Go to (6)

(4) If (1f1< Is discrete) go to (7)

Wk := first smallest ce1l of 11"1<

Vk:= min W~

If (dig = tru.e or 1I"k i'! P) hh:= k +1

ek:= 0

Go to (2)

(5) Z!k := zb k := A;,

Go to (4)

(6) Ie' := k

69
 "" := 1I1nthh-l, IIIU:{M - 1, [Link]}}

If (k' = hh) go "to (3)

1:= 1I1n{1 + 1, L}
AJ- := IIlCr (fI'IoIl)

"'r := flx(fI'llll )

Go t o (12)

(7) It (II. = 0) g o "to (18)

I f (k ~ [Link]) go t o (8)

Define 1 E' Sn by (' = /I

If ((71 = G) go "to (10)

(8) If (Illb = ja.l&e or qzb < 0) go to (Ol

If (q;d >0 or k < Ipl) 80 t o (9)

I f (G(") > G(p)) go to (9)

If (G(") < G(p)) go to (Ol

Define 7 IE S" by (,1'1 = p

Go to (10)

(9) p := II

qzb := 0

hI; := hzb:= Ie

zb" +1 := 00

Go to (6)

(to) 1: = min{l + 1, L}
(h := IIcrb)

flr: = flxb)

If (8b) < 0) g o to (11)

"
 O:=OvO(-r)

Output '1

If (ttiC e lIler(O}) go to (11)

k:= II.

Go to (13)

(11) k := hb

(12) If (ek = 1) Wk:= Wknn,

(13) If (k ~ 0) stop

If (k> h) go to (17)

If (k=h) go to (14)

II. := Jt

ttiC := ttlh. := min WI;

(14) If (tlk and ttlh are in the same cell of 0) indllx := indllx +1
1110 := mini tI e W" I II > tlk}
If (1110 = 00) go to (16)

If (tlk tL mer(O}) go to (14)

(15) 11.11.:= min{hh., It + 1}

h.z!:= min{hz!, k}

If (lab = falsll or hzb < It) go to (2)

hzb:= It

qzb := 0

Go to (2)

(16) If (IW,,! = 'ndex and ht = k + 1) h.t:= k

size := size X index

index:= 0

71
 .I::=Jc - 1

Go t o (1 3)

(17) If (ek = O) set Wh:= Wknn , for each i, l<i < l, such
t hat (1I 1, V2' ··· , Vk _l } C tIJ,

11k := min{ tI e Wk I tI > tlk}

If (v. ~ 00) go to (5 )

.1::= k-l

Go to (13)

(1S) h := ht := hzf := k

!:= II

k:= .1:-1

I f (1t1h = f al/e) go to (13)

p :=v

hzb := hb := k +1

qzb := a

Go t o (13 )
o
2·32 Con sider the stage during t he execu tion of Algo rl tb.
2·31 tha t
ve pas s the poi nt marke d B (1n Step (la». At t his instan t define
K = k - l and "W. = tI. (1 <i< K ).

Now l et r IO) = r = Aut(G ),., and define r ei) = r .. 1 • • a•...• "'1

(poin t-
wi s e stab i1 1ser) for 1 < i< K. Since r is a termi nal
node, the coars est
e<tult able parti ti on which 1s finer t han 'If and thes Wl
,W2, · ··, WI( i s
discr ete. There fore r (K) = 1.

71
2·33 Theorem During th.e e:tecut1on of Algo";thm £·91, each. timt we pas,
point A (in Step (16)) or "o,'nt B (in Bte" (18)) th.e foj/owing are trut:

(1) inde:t = Ir (I<-lJ\/lr(")1 (point A orull)

(i 1) size = Ir (lH)1

( 1.1 1) 8 = 9(r ( · - I ~

(t v) r (I<-l) = (Y}, when: Y i$ the lit of a.U automorph,',m, output

up to tht! "ruent stag e (in Step (10)).

(v) IYI < n-I'I

Proof: The theo re ll f ollows r eadily fr om t he theo r y that we bave already
discussed, so we will only descri be br iefly how this need s t o be assellbl ed.

PO int B is only passed once, whe n, i s c reated, and It = K +1

at this stage. Point A is then passed K tilles, at which stages Ie has
the values K,K-l,"' ,11n that orde r.

We prove the t heore. by backward Induction on 1;. For Ie = K +1

it is obvIous. Now assu.e it for 11;' , f or so.e Ie' , 2 <11;'< K+l. and
let .1: = .1:' - 1.

Consider v = \11"1,'11"2, "',11".1:1. The successor s of 11, in the

order earliest to la test are III,V2, ··· .11... wbere II. = II(W.). and WI< =
{WI,W2, ···,ur... }. The p r evious ti.e we passed pOint A (or B) was Whe n we
completed our examina tion of the subtree T(G .'II", 1I1)' We now clai ll that,
for 1 < i < m, by the time we ha ve completed exami nation of T{G,1I",1I;).
Wi is in t he same cell of 8 as WI if and onl y i f II; "-J 1-'1.

Suppose on the contrary t hat there is an earliest v, for whic h

our asse r tion is not true. If v; i s not equivalent to VI then w. a nd WI

are obv iously in different cells of 6, !o ince 6 Is the orbit partition

of so.e subgroup of Aut(G) ..,. On t he other hand. i f 11,,..,/.11, T(G,1I",II,)
contai ns one or more terminal nodes equi valent t o !. The nature of the
algorithm 15 such that if one of these nodes is generate d, it 10'111 be
recognized 4S being eq ui valent to " and if it is not generated t hi s will
only be because i t has been shown to be equiva l ent to an earlier terminal
node. FurtheTllore, i _p Ueit [Link] are neve r used t o reduce WK.
Ilnd during the examinati on of T(G,1I", 1I;), if any , the only stored pair s

n
(1/1';. OJ) which are used to reduce any W. have WI E ~i' Therefore, e1 t her
Wi is already In the sallie cell of 8 a s Wt or we are sure to discover
so.e a utollOrphl s. "l s uc h that vI < IIi. By the Induction hy po t hesis wI
is In t he salle cell of 9 as W I> and so 1:he upds.1:e 8 := 8 v 8(,} merges
the cell s of 8 contain I ng WI and Wi, c ont [Link] to hypothesis. No te a lso
1:hat we ha ve J ust proved t ha t '1 e Y.

We have thus concluded tha t the cell of 8 contai ning WI is

the orbit of r (Jo- I ) contain ing WI' Since (I = 9(Y) by construction,
and r (Joj < (Y) by the o riginal induc tion hypothesi s , we .ust have
r (k -l )= (Y). since (Y) contaIn s a fu l l set of coset- r e presenta t ! ves f or
r(k) in r (k-l). This proves that 8 = 8(r (k-l» ). The [Link] inde:t merely
counts the [Link] of elements In the cell of /I [Link] i ng WI . so clahs
( 1) a nd (i1) fo llow i mmed i a. t ely.

Claim (v) f oll ows fr ail the s impl e observation tha t t he [Link]
of ce lls of 6 s tarts at n and decr eases by at. l east one f or each new
element of Y. o
In cl osI ng we note a few s imple prope rties of the s et of
generato rs of r f ound by Al gorttb:l 2·3 1. These are essentiall y the sallie
as those given in Theo r e ms 35- 38 iu [13] and t he proofs given t here a pply
with only notati onal cMnges. Let Y be the full set Of auto tlo rp hls.s
output by Algorith. 2·31, and let r = Aut (G) .

2·34 Tbeonm (t) Y d(l t l not comain ~ny elements of the form ,.,6, wh.!re
1,6 E r, supp(,)n supp(5) = 0 an.d" -:I:- (1) rf 5.

( 2) SUPPOIe ,hat fo r lome su6,et Y· C Y , we have (y.) = (Al l), . .1.(1)).

where A (I) and A (2) are [Link]-trivial subgroups of r with [Link] support. Then
y. = y ell u y (2) , where y (ll n y(l) = e , (y(t» = AP) and (y(ll) = A(l).

(8) Suppose that for , orne suhet W C V the point-wi'! stabiliu r

rw hal oNY ont no n-trivial orbit. Th en . ome ,1£bsd of Y gener4t u a con.-
jugate of rw in r . 0
IMPLEMENTATION CONSIDERATIONS

In this section we will discuss sOllie of the problems that arise in

the implementation of Algorithm. 2·31 and how these have been approached.
We will then examine the theoretical and empirical performance of our
implementation. Finally, we wJll mention a few of the practical uses
to which our implement ation has been put.

3·1 Time versus storage

The program described in McKay [14] worked so efficiently for

many classe s of graphs that the practical limit on the size of graph
that could be proce s sed was set by the amount of storage Ilvailable,
rather than by execution time considerations. Consequently the present
implementation places rather more emphasis on storage conservation, in
some places to the sl ight detriment of time eff i ciency.

The variable types used by Algorithm. 2·31 include graphs, sets,

partitions and parti tion nests. We will now describe the data. structures
used in our implementation for each of these variable types.

3·2 Partition nestl

Let v = [1I"1,1I'":1, "', 1I"1<[ e .JY(V). Then v can be represented by two

arrays a. and b of length n as follows. Define 11"0 = (V).

(1) The array a contains the elements of V in any order

consistent 11'1 th 11"1<' Precisely, i f u(a(i),1(... ) < u(a(J1,1(",)
then i < j, for any;, j E V.

(11) Each entry of b is an integer in the i nterval [0, n+ 1[

chosen thus:

(a) Ifu(a(i), "Irk) = u(a(i + 1), "Ir,,), then b(i) = n +I

(1<i<n-l).

(b) If u(a(i),1I"H) _ u(a(i + 1),1I"j_l) but u(a(~),1'T"j) <

u(a(1+ 1),"lrj), then b(i) = j C1 <j < k, 1 <i< n-lJ.

(c) bin) = o.

75
 3·3 Unord ered partit; ionl

The only unord ered partit ion used by Aljo ritlm 2.31 Is
Fore.
any v e. V let 8. denot e the cell of e
conta ining " and let p(tI) = ain8...
Clear ly e
can be uniqu ely repres ented by the array p, and most of
the
neces sary quest ions abou t S can be answe red very quick
ly by refere nce
to p. For examp le, if 11, 'W € V then 11 and 'W Ilre In the
salle cell of
8 if and only if 11(,,) = p{w), and 11 E acr(S) if and only
i f p{,,) =".
This repre senta tion of 8 suffe rs fro. the dlsadv l.\ntag
e that
updat es of the form S;= SvO(-J), for 1 € S ,,' are quite expen
sive in terms
of computat i on tille . This proble lll has been cons i de rably
a ll ev iated by
the use of a second a rray q whlch "chain s together~ the
eleme nts of each
cel1. More precis ely, if i € lIIcr(S). the n S. = {i. q(,), q(q(t),
"q(q(q('ln. · ·· },
where the s equen ce termi nates on the te rm before the first
ze ro.

3·4 Graph .

[Link] lthm 3·3 1 requi r es the input graph G and, for reason
ably
effic ient opera tion, requi res the gra ph varia ble G(p).
Froll t he great
number of possi ble ways of repre sentin i these graph s in
the compu ter, we
Ilave chosen All adjac ency l:l4trl x repre senta tion becau se
of It s great er
storag e economy. More precis ely, G is stored as a list
of n blt-
vecto rs repre senti ng N(1,G), N(2,G). ··· ,N(n, G), and so
requi res around
n 2 bits of storag e. Since Algor ithm 3·31 i s valid also
fo r digrap hs, it
1s clear ly Dot possib l e t o reduc e t his storag e requir
ement in gener al.
However "if the prog ram was only 1ntenr ied to be apPlie d
an graph s with
ve ry loW' degre e, a dlf f e r en t so r t of repre senta tion would
save space ,
and proba bly time as wel l.

J·S ElHciency of Algor ithm 2·5

Algor ithm 2·5 can easily be implem ented usi ng the data struc
ture s
above . We '01111 now consi der tbe effici ency wbich can
be a c hieved i n
such an Imple menta tion. The follow 1ng complex1 ty resul
t wa s sugge sted
by a re18te d resul t 1n Gries [ 7] . For t he neces sary defin
iti ons , r e f er
back t o Secti on 2·9.
J·6 Theorem For 4ny G E Q(V), fr IE LI(Y) [Link] dirlinct 111, 1Iz, " ' ,11... _1 IE
V, the deri1led partiti on nut l'lrl,1rZ,·· ·, 'lrml can b. computed in O(n:l l og n)
time, auuming an impl.m entation in which. .i(1I, W ) can be computed in time
proportional to IWI, for an~ v IE V, W C v.

-Proof: It Is obvio us tha t the time occupi ed 1n t he computation of 'II", otl;

for 1 <i< m - l and 1n Step (1) of Algorithm 2· 5 w111 be O{n 2 ). Since
eac h e~ e cutlon of Step (2) of Algorithm 2· 5 req ui r e s onl y a fi~ed amount
of ti me and l eads to a n e lec utio n of Ste p (3 ) , we are j ustifi e d 111
r es tr icti ng our atte nti on to Step ( 3 ).

For a ny gi ven W, the nec essllry r exeeuti ons of Step (l) can be
performed in O(nI W I) t i me. Therefore the total time for the comp utation
of l'lrI, 'II"~,·· · , 'II"",lis O(n2+nEIWI), where t he sum 15 over all sets
a s si gned to W during any execution of St ep (2) (f or any execution of
Algorithm 2·5).

Le t :0:; IE V and consider t he real varIa bl e q." defined Ilt Il ny

point of tiDe d ur ing any e xecution of Algorithll 2· 5 by q:z = As l ogzl.,. +
He r e hs i s the number of s ets contain i ng :t whi cb bave bee n previ ous l y
a ss Igned to W d ur i ng a n execution of Ste p ( 2) , pl us t he nUllber of se t s
Wi (m <j < M ) which [Link] tain :t, plus one fo r the se t {:t} = {tid
created by t he operation '11";0'11;, i f it exists and has no t already been
counted. Also l~ i s the current size of t he cell of 1f which contains
z. Note that h~, l~ aM. q,. are var iabl es which f r equentl y change value
during [Link] ri th. 2·5.

The value of q., c lea r l y reDlll i lls constant or dec reases betwee n
dIffe r ent exec utions of Al s or i thm 2·5. The ool y other place where i t can
cha nge is dur i ng St ep (3) , when ha reDlll i ns fixed whl1e (II decreases, Of

h.~ i ncreases by on e. I n t he latter cllse I", de c r ea Se S by at l east a fac to r

of two, so tha t q~ d oes not increase. Therefore qa i s non- increasing
throug hout the cOllputa ti on, implying that its l a s t va l ue is bounded
above by it s first , which Is bounded above by 2+1og~n. Therefore the
final value h,,,, of h." I s at lIIoSt 2 + l og2n.
We c onclude tha t the t otal t iae requ i r e d f o r the computa ti on
+
of ['11" 1, 11"2, • • •, '11" ... 1 is O(n 2 n L:OEV~) = O(n 2 10g n), 8.S requi r ed. 0

77
 Por our particular choice of data structures, and our part icul a r
implemen t a t ion environmen t, we have found that the fastest way to compute
d(v, W} for ",/30 <
IWI < A approxilll4tely 11$ to represent W as a bit-
vector and t o count the numbe r of one- bi t s in the bit-vector re present ing
N(v ,G) nW. Altbough this t echnique (used for IWI > n appears to r ed uce
t he t otal the in - t he aajarity· of c ases, 1t has t he unfortuna t e side-
effect of invalidating the pre mises of Theo r ea 3·6. The be st [Link]
for the bound 0(n 2 10gA) which we have been able to prove I s O(n ~).
Since the time require d for the computation of d(v, Mr) is now essenti ally
independent o f IWI, Step (3) o f Algorithm 2·5 can be simplified by us ing
t = 1. This is espe cia lly conven ient if t he seq uence a is r epresented
as a set at poin t ers to t he array a (see Sectlon 3·2) .

3· 7 Efficiencyof' Algorithm 2·31

Le t T·(G,1f) be a portion of t he search tree T(G ,1I') wh ich Is

examined by Al go rl thll 2·31. Le t ffll be the nUllber of t eril i nal nod es o f
T-(G,1f) whic h are e qUivalent t o t he earli es t [Link] l node r (incl ud i ng
r Itself) . Let m2 be the n\lllbe r of nodes of T-(G,l'f) which are not
equival ent to ~ and whi ch do not have any des cendants In T-(G, 'II'). Let L
be the constant defined I n Section 2·30 . The n the total time r e~ul red by
Algor 1 t hm 2·31 is O(m l "'~ log", + m2A2(L + log A)), under the conditions
01' Theore. 3·6, Where m~ aay depend on L. For our h p l [Link] tlon, this
lIIust be increased to O{n (m l 3
+ ",2) + m2",2L). By Theore. 2·33, ml < n,
but we hav! not fount! any reasonable bound on "'2' It varie s 1n a ve ry
compl icated manner wi t h the initial labelling of the input gra ph and
the val ue of L .

3·8 Other implementation detail,

Algor ithm 2·31 has been [Link] on a eyber 170 computer,

lII4inly i n Fo rtran. Because of the diffi culty 1n manipulati ng b i t- vectors
e ff ic i e n tly 1n Fortran, several small subroutines a re coded in asse mbler
language.

The ind ica tor func ti on A Is e valua ted b y the s ub r ou t ine which
1mplements Algo rlt hll 2·5. It Is f ormed by taU ng cell s i zes, relative
ve rt ex d eirees and other inf ormation .... hi ch 15 computed 1n the course

"
of Algori thm 2·5, and merging these into Ii single integer value in a
"random" fashion (see Section 2·28).

A technique which produced considerable improvements in ef-

ficiency in some cases involves the updating of the graph G(p) when p is
updated. The computation of G(p) is quite time-consuming (up to about
6 seconds for n = 1000), so this computation is delayed for as long as
possible, in case it is not necessary.

]·9 Storage requirement!

Let m be the number of machine-words required to hold a bit-

vector of size n. Let K be the maximum length of a node of T*(G,1r).
Obviously K::; n, but very much smaller values are normal. Define L as
before. The total amount of storage required by our implementation, ig-
noring Ii minor amount independent of n, is 2mn+ IOn+m+ (m+ 4)K +2mL
words. This figure includes 2mn words for the storage of G and G(p).
If Ia.b = faiae (see Algorithm 2·]1), the storage requirement is reduced
by mn + 2n words.

3· 10 Experimental performance

In figure 3·1 we give the execution tiJlle required for several

faJllilies of graphs. In each description below, f} gives the approxilllate
slope of the curve in the region 50 < n < 200. Al though the resul ts of
Section 3·8 predict 8. value of /3 >4, even when m2 = 0, the experimental
value of f3 is less than 3 in each of these classes.

E empty graph on n vertices (f) = 2·8).

Q m-dimensional cube, where n = 2'" (fJ = 2·3).

C randoJII circulant graph of degree 10 (f3 = 2·2). This 15

defined by V(G) = V and E(G) = {zy liz - yl E W(mod n)},
where W is a random subset of {I, 2, " ', l(n-l)J2J} of size
5.

R~ "random n regular graph of degree 6 ({J = 2·9). There

is no known practical algorithm for randomly generating
regular graphs so that each graph appears with equal

"
 100
Q c

u~
io
s,, ~onds

10

/
G, /
/
/p
/
/
1 /
/
/
/
/
/
/ G,
/
/
/
/
/
/
-1 /
/
/
/
/
/

/
/
/
/
- 01 ~____~~~~.-~/~~~,-____~__~-.-.-.~~.
10 100 lODe
nWllber o f vert ices
Figure 3· 1

"
 frequency. The graphs represented by the curve R~ were
made by randomly generating three permutations '71, '72 and
'7 ~ E S .. such that :r;6 ~:r; c6 E b~,'7~,'7n) and :r;1'i rf :r;'l1
(1 <i < j < 3) for each x E V. Define G by V(G) = V
and E(G) = {xx'l; 1 x E V, 1 <i< 3}. For n > 40 all those
graphs constructed had trivial automorphism groups, and
produced search trees with maximum depth 2.

R 20 : same as R~ but with degree 20 (f3 = 2·6).

G1 random graph (f3 = 2·0). Each possible edge is independ-

ently chosen or not chosen with probability!. The dashed
line marked P in figure 5·1 gives the average time required
for the computation of G(p) for some p. At least one
such step is essential for any program which computes
C(G,:rr) from G using an adjacency matrix representation.
Therefore figure 3·1 suggests that the performance of our
program is close to optimal for large random graphs.

G2 same as Gl but with lab = false.

3·11 Harder examples

We have also tested our program on a number of graphs which have

traditionally been regarded as difficult cases for graph isoJ[lorphism
programs.

(1) The strongly regular graphs with 25 vertices required

between 0·1 and 2·4 seconds, with the average time being
1·0 seconds.

(11) A strongly regular graph G with 35 vertices can be formed

from a Steiner Triple System (STS) with 15 points. The
vertices of G are the blocKs of the STS, and two vertices
are ad j acent if the corresponding blocks overlap. For the
80 graphs so formed, our program required between 0·3 and
7 seconds, with an average of 4·8 seconds. Most of these
graphs have a trivial automorphism group.

(iii) Certain strongly regular graphs G with n vertices can be

extended to graphs E(G), having 2n+2 vertices, which are

81
 2'/e1Jel regular (see Mathon tl 0J ) . There are good theoreti -
cal reasons aD] t o expect 2- level regula r g ra phs to be
parti cula r ly dl ftlc ult to pr ocess, and this Is bor ne out
by e xpe rie nce. The graphs Aeo and B no (60 ver ti ces; see
[10]) requi red 79 and IS O seconds r e spective ly, while the
graphs A72 - D 72 (7 2 verti ces) require d about 500 seconds
each.

3· 12 Duign ilomorphism

A de8ign D (al so kn own as a hypergraph) is a pai r of sets

(P , B) • .... he re 8 1s a collect ion of subsets of P. The e lements of P
a re called [Link] aod the elements of B are called 61oclu. Two de s tgns
Dl = (PI, B 1) and D2 = (P2, 8 2) are i somo rphic if there are bijecti ons
h : P I -+ P~ and h: BI -+ B2 s uch that :c e X implies h(:c) e 12(X) f o r
all :cePI and XeB I •

Gt yen a design D = (P, B) .... e can constr uct a gra ph G = G(D),

.... here V(G) = P U B and E(G) = {:cX [ :teP,XeB, :teX}. I t is easy
t o prove ([3), [17)) that two designs D\ =
(PI, E I ) a nd D2 = (P2, B 2)
are isomor phic if and onl y if t here is an isomorphl s. I : G(D l ) - I ' G(D2)
such t ha t IIPI) = P~ and I(B 1 ) = 82' Therefore Algor i thm 2· 31 can be
used for design isomorphism.

If D I s a balanced incomp le t e hl ock-design (S ISD) then G(D)

i s known t o pres ent difflcul t1 es for many graph i [Link]. progra.s.
a nd ours is no exception. TlIo SO-vertex g ra phs G(D), na.e d A~ a oe! B 'j,O
i n [10J. r equi r e d about 60 seconds each. In a nother expe rhe nt (181, we
established t he isollo r phisll of six BIBLTs with 36 points and 36 bloc ks
(so n = 12) us i ng about 6·6 seconds of lIachine time each. The smallness
of thIs f igure is principally due to tile reasonabl y r ich aut ollorphism
g r oups of t he designs .

A lIuch more d iffi~ult problem posed by two BI SDs wt~h 126 points
and 525 blocks has be en previ ous ly disc ussed in Stanton and McKay (17].

3· 13 Hadamard equivalence

Let M .. and M2 be two m X n matr i ces with ± l entries . We sa.y

tha.t Ml and M~ are [Link] equilJa/mt If M2 can be obtained ·f ro m
Ml by app l yIng an e l [Link] of the group r generated. by the follow i ng
operatio ns.

,. Permute th, ro ws according to Q E Sm.

Permute tho ~olumns according to (J E 5".

" Mul tipl y rowiby-l (1 <i < m).
"
'I Mul Upl Y col uan j by -1 <1<j<n).

Suppose t hat M 1s Any mXn IIlI trlx w!'th ± 1 entries. Deflne G=

G(M) to be the graph witb V(G) = { 'II;,D;,Wj,~j 11 <i< < j < n}
m, l
and E(G) = {'II,'Wj, D,1UI 1 1 < i < m,l < j < n, M' j = I} U {'II,W;, D;Wj I
1 <i < m, 1 <j< n, MIl = - I}. We will refer to the vertices I), and !Ii
as I) ·type'llerl;ices. The following theorem first appeared in McKay [16].

3·14 Theorem Let G 1 = G(Mll [Link] G 2 = G(M~). Then Ml a.'I1.d M~ are

[Link] equil)alent l' [Link] only if [Link] i, a.n [Link] h,iJm f Tom G 1 to G ~
which. maps the v-type tlerhcu of GI onto thOH of G 1 . o

If M is a I(ada,mard Datrix (m = 110 and M TM = fl./) then the

iraph G(M) llIay prove exeeedingl y difficult for A.lgorith_ 2·3 1. This was
discovered when our implementation was applied to a collection of 126
Hada mard matrices of order 24 , produced by t. Dibley and W. D. Walli s , in
an attempt to determine the equival ence classes. Several of the graphs ,
havlni la rge automorphism groups, were processed In about 300 seconds,
but some of t bose witb small e r automorphism g r oups wo ul d requi r e .ore
than 1800 seconds - the prog ram was not run to c ompletion. These graphs
are all 2-Tevel regula r In the sense of Mathon (1 01 , but are ve ry lIucb
harde r than those given in [10 1, even thougb the~ have larger groups. Tbe
reason for this is that the sea rch tr ee T"(G,'If) has depth 7 or 8 (colllpared
with 4 for the graphs in {l Oll, al thoug h only 2 or 3 vertices generally
need to be fixed In order to eli mi nate any non- triviAl automorphlsms.
This means that the automorpbism group Is of no use for a large part of
T"(G, '11').

Other ~orkers (see 16] for eXBIple) have found t hat a count of
small subgraphs (e. g. cllques) can ofte n be used to provide an inl UaI

8J
pa r titioning of tbe vertices of a. d i fficult gra ph, wbi c h greatly spee4~
up a subsequent i somorpbi s m test. Siailar techniques can be usel1 bere,
but they are of no use in [Link] cases. SOlle of the hardest graphs aacmgst
the 126 ment ioned above have only two orbits (the v-type vertices and the
others) - the inltlal partitioning which we were usini anyway (because of
Theorem 3·15). However we have devised a me thod based on a generalisati on
of the profile l1et1ned 1n [51 Which can be used to refine the partition s
at the illmedlate s uccesso rs of the root node 1n T-(G,1T). With this
impr ovement, we can now process t hese graphs 1n about 20 seconds on the
average.

An a lgorithm s pecifically for equivalence of Hadaaard !latrices

has been definel1 by Leon [9] . The details given 1n [9] are insufficient to
perllit a direct compari son with our technique, but a cursory exallination
suggests that Leon' s t echnique may be competitive with ours for this
particular proble •.

EXAMPLES

In t his secti on we give twn exallp l es of t he automorphism group

generators prol1uced by Algorithll 2·31. I n each case we w11 1 use the
notation defined in Section 2·32.

4·1 First example

In our fir st example G is the S- dll1en sional cube defined as

fo ll ows.

V(G) = {(i, i , k,l, m) I i,;, k,l, mE {a, I} }

+
E(G) = {(i l ,i1 . kl' h, m l)(h.;h, k2, 12. m 2) I (il - i2)2 (il - h)2
+
+ (k l - ..t2)2 (h - b)2+ (ml_m2)2 = I}
The elements of V{G) are numberel1 1.2,···.32 in lexicographic order .

For this graph we find K = 5, Uil = 1, W2 = 16, w~ = 24,

W~ = 28 and w~ = 30. The output produced is as below. The execution
time WIiS 0· 18 s econds.
(3 5 ) (46 ) (11 lJ ) (12 14) (19 21) (20 22) (27 29) (28 3D)
Ir(f)l = 2 1B(r" ')1= 24

..
(2 3) (6 7) (10 11) (14 15) (18 19) (22 23) (26 27) (30 31)
Ir(~;)1 = 6 18(r{3»)1 = 16
(S 9) (6 10) (7 11) (8 1 2) (21 25) (22 26) (23 27) (24 28)
Ir(2)1 = 24 18(p(2»)1 = 10
(9 17) (10 18) (11 19) (12 20) (13 21) (14 22) (15 23) (16 24)

W'''I = 120 18(r"'11 = 6

(1 2) (3 4) (5 6) (7 8) ( 9 10) 01 12) (1 3 14) (15 16) (17 18) (19 20)
(21 22) (23 24) (25 26) (27 28) (2 9 30) (31 32)
_ 3840
WI 1

4·2 Second example

In our second exampl e G is the lexicographic product C~lC31

defined as follows.

V(G) = {(i, j) 11 < i,j < 5}

E(G) = {(ii, jI)(i 2, :h.) IIi1 - i21 =
l(mod 5) or
i 1 = i2 and Ijl - J~I = l (mod 5)}
The vertices are labelled 1,2," ' ,25 in lexicographic order.

For this graph we find K = 10, WI = 1, W2 = 3, W3 = 11,

W, = 13, W~ = 16, Wr; = 18, WT = 21, Ws = 23, Wg = 6 and WlO = 8. The
output below was generated in 0.23 seconds.
(7 10) (8 9)
Ir(g)1 = 2 1e(r,O')1 = 13
(6 7 8 9 10)
Ir(S)1 = 10 1e(r"')1 = 21
(22 25) (n 24)
Ir(T)1 = 20 1e(r"')1= 19
(21 22 23 24 25)
Ir (~)1 = 100 1e(r"')1 = 17
(17 20) (18 19)
Ir (~ )1 = 200 1e(r"')1= 15
(16 17 18 19 20)
Ir(4)1= 1000 1e(r" ')1= 13
(12 15) (13 141
Ir(~)1 = 2000 1,(r"')1= 11

"
(11 12 13 14 15)
(6 21) (7 22) (8 23) (9 24) (10 25) (11 15) (12 17) (13 18) (14 19) (15 20)
rr(2}1= 20000 IO(r(2)1 = 7
(25)(34)
[r(I )1 = 40000
(12345)
11 15 21) (2 7 12 17 22) (3 8 13 18 23) (4 9 14 19 24) (5 10 15 20 25)
_ 1000000 IW)I 1

REFERENCES

[1] V. L. Arlaza r ov, 1. 1. Zuev, A. V. Uslcov and I. A. Paradzev: An

algorithm for the reduction of finite non-oriented graphs to
canonical form. Zit. 1.!!Jchisl. Mat. ma.t. Fiz. 14, 3 (1974)
737-743.

[2] T. Beyer and A. Proslcurowslci: Symmetries in the graph coding

problem. Proe. NW76 ACM/CIPC Pac. Symp. (1975) 198-203.

[3] C. Bohm and A. Santol1ni: A quasi-decision algorithm for the

p-equivalence of two matrices. ICC BULLETIN 3, 1 (1964)
57-69.

[4] J.A. Bondy and U.5.R. Murty: Graph Theory with Applications,
Macmillan (1976).

[5] J. Cooper, J. Milas and iI.D. Wallis: .Hadamard equivalence.

International Conference on Combinatorial Mathematics, Canberra
(1977), Lecture Notes in Mathematics 686, Springer- Verlag
126-135.

[6] D.G. Cornel1 and R.A. Mathon: Algorithmic techniques for the
generation and analysis of strongly regular graphs and other
combinatorial configurations. Annals of Discrete Math. 2 (1978)
1- 32.

[7] D. Gries: Describing an algorithm by Hopcroft. Actalnformatica.

2 (1973) 97-109.

86
[8) J. Hopcroft: An nlogn algorittm. for minimizing states in
a finite automaton. Theory of Machines and Computations.
Academic Press (1971) 189-196.

[9J J.s. Leon: An algorithm for computing the automorphism group

of a [Link] matrix. J. Combinatorial Theory CA) 27 (19H)
289-J05.

[10} R. Mathon: Sample graphs for isomorphism testing. Proc.

9th. Southeastern Con/. on Comb., Graph Theory and Computing
(978), to appear.

[111 R. Mathon: Personal communication.

[121 B. D. McKay: Backtrack programming and the graph isomorphism

problem. M. Sc. Thesis, University of Melbourne (1976).

[13] B. D. McKay: Backtrack programming aM isomorph rejection on

ordered subsets. Ars Combinatoria 5 (1978) 65- 99.

[14J B.D. McKay: Computing automorphisms and canonical labellings of

graphs. International Conference on Combinatorial Mathematics,
Canberra (1977), Lecture Notes in Mathematics 686, Springer-
Verlag, 223-232.

[IS] B. D. McKay: Topim in Computational Graph Theory. Ph. D.

Thesis, University of Melbourne (1980).

[16] B.D. McKay: Hadamard equivalence via graph isomorphism. Discrete

Math. 27 O!n9) 213-214.

[17] B.D. McKay and R.G. Stanton: Isomorphism of two large designs.
Ars [Link] 6 (197B) 87-90.

[18] B. D. McKay and R. G. Stanton: Some graph isomorphism computa-

tions. Ars Combinatoria, 9 (1980) 307-313.

[19] H. Wielandt: Finite [Link] [Link]. Academic Press (1964).

"