M840 Dissertation in Mathematics

Moore Graphs

Sanjeev Gupta
B0524984

Submitted for the MSc in Mathematics

The Open University
Milton Keynes UK

16 May 2014
Contents

1 Introduction 3

2 Elementary Properties 5

3 Diameter 2 8

3.1 Uniqueness of the Moore graph of type (3,2) . . . . . . . . . . . . . . 11

3.2 Uniqueness of the Moore graph of type (7,2) . . . . . . . . . . . . . . 13

4 Properties of Moore graphs of type (57, 2) 19

4.1 Counting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.2 Independent Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.3 Vertex-Intransitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3.1 Feasibility Condition for Automorphisms . . . . . . . . . . . . 23

5 Diameter 3 28

6 Convex Cycles 30

6.1 Odd Convex Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6.2 Even Convex Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.3 The Combined Inequality . . . . . . . . . . . . . . . . . . . . . . . . 36

B0524984 1 Sanjeev Gupta

CONTENTS 2

7 Conclusion 38

Bibliography 39

B0524984 Sanjeev Gupta

Chapter 1

Introduction

In this dissertation we consider the classification of Moore graphs. In 1960 Hoffman

and Singleton [9] investigated Moore graphs of diameter D = 2 and 3, showing
that for diameter D = 2 unique graphs exist for degree d = 2, 3, 7 and possibly for
d = 57 but for no other degree. For diameter D = 3 they showed that the unique
Moore graph is the heptagon with degree d = 2. They called such graphs "Moore
graphs of type (d, D)". In 1973, Damerell [5], and independently Bannai and
Ito [2], showed that no Moore graphs exist for diameter D ≥ 3 other than the
(2D + 1)-sided polygons. Thus from [9] and [5] we have the following results:

Table 1.1: Moore Graphs

Degree Diameter Name
d 1 Kd+1 Complete graph
2 D (2D + 1)-gon
3 2 Petersen graph
7 2 Hoffman-Singleton graph
57 2 Missing Moore graph

Neither the existence nor uniqueness of Moore graphs of type (57, 2) is decided
even to this day. Although the other Moore graphs are vertex-transitive, Higman
showed in the 1960’s that a Moore graph of type (57, 2) cannot be vertex-transitive
and more recently Mačaj and Širáň [10] have shown that the order of the
automorphism group of any such graph is at most 375 if the order is odd and at
most 110 if the order is even, both bounds being considerably smaller than the
order of the graph.

B0524984 3 Sanjeev Gupta

1 Introduction 4

We shall start by investigating some elementary properties of Moore graphs

proving various results about their structure. Following the treatment of Hoffman
and Singleton [9] we prove the existence and uniqueness of Moore graphs of
diameter D = 2 and degree d = 2, 3, and 7 and show that the only other possible
degree is d = 57. If a Moore graph of type (57,2) exits we shall show that an
independent set C has size at most 400, and if a set C of this size exists then each
of the 2850 vertices not in it is adjacent to exactly 8 vertices in C, cf. Godsil and
Royle [8] p. 100. It is considered that such results, when compared with other
known graphs, may lead to a construction for a Moore graph of type (57,2).
Following Higman we shall show that if a Moore graph of type (57, 2) exists then it
is not vertex-transitive. We also prove that the unique Moore graph of diameter
D = 3 is the heptagon.

To conclude we look at a different characterisation of Moore graphs based on the

number of convex cycles they contain due, more recently, to Azarija and
Klavžar [1].

B0524984 Sanjeev Gupta

Chapter 2

Elementary Properties

Let X be an undirected graph without loops or parallel edges, called a simple

graph, with n vertices, maximum degree d and diameter D. Let ni for
i = 0, 1, . . . , D be the number of vertices at distance i from a distinguished vertex
u of X; we say such vertices belong to tier i. Then n0 = 1, n1 ≤ d and since any
vertex at distance i from u can be adjacent to at most d − 1 vertices at distance
i + 1 from u,

ni+1 ≤ (d − 1)ni and (2.1)

D
X
n= ni ≤ 1 + d + d(d − 1) + . . . d(d − 1)D−1 (2.2)
i=0

2D + 1 if d = 2,
= (2.3)
 d(d−1)D −2 if d > 2.
d−2

As stated in [9] E. F. Moore posed the problem of describing graphs for which
equality holds in (2.2). He noted that when equality holds we must have
ni+1 = d(d − 1)i for i = 0, 1, . . . , D − 1 and so X is d-regular. Furthermore, each
vertex counted in ni is adjacent to precisely (d − 1) vertices counted in ni+1 for
i = 1, 2, . . . , D − 1 and hence no arc joins two vertices equally distant from some
distinguished vertex except when they are both at distance D from the
distinguished vertex. Thus the girth g of X is (2D + 1).

Alternatively, following Damerell [5], let X be a graph with n vertices, minimum

degree d and odd girth g = 2D + 1. An argument similar to that above gives
n0 = 1, n1 ≥ d and any vertex at distance i for i = 1, 2, . . . , D − 1 from u has 1
neighbour at distance i − 1 from u and none at distance i from u, as otherwise

B0524984 5 Sanjeev Gupta

2 Elementary Properties 6

there would be a cycle of length at most 2i + 1 < g - a contradiction. Hence each

such vertex has at least d − 1 neighbours at distance i + 1 from u. Similarly a
vertex at distance i + 1 with i < D can have only one neighbour at distance i from
u as 2(i + 1) ≤ 2D < g and hence
D
X
n≥ ni ≥ 1 + d + d(d − 1) + . . . d(d − 1)D−1 (2.4)
i=0

2D + 1 if d = 2,
= (2.5)
d(d−1)D −2

d−2
if d > 2.

When the lower bound is attained X is again a Moore graph with girth g and
diameter D satisfying g = 2D + 1. We thus have the following from
Cameron [4] p. 181:

Theorem 2.1. Of the following conditions on a graph X, any two imply the third:

• X has maximum degree d and diameter D;

• X has minimum degree d and girth g = 2D + 1;


2D + 1 vertices if d = 2,
• X has D
 d(d−1) −2 vertices if d > 2.
d−2

Singleton [12] proved that any graph whose girth and diameter satisfy g = 2D + 1
is regular; see also Godsil and Royle [8] p. 90. As pointed out by Cameron [4], the
first two conditions above also show that a Moore graph is regular.

Thus an equivalent definition of Moore graphs of type (d, D) is graphs with

diameter D and girth g = 2D + 1.

In addition to regularity, Godsil and Royle [8] p. 91, proved:

Theorem 2.2. A Moore graph is distance-regular.

Damerell [5] used the theory of distance-regular graphs to show that there are no
Moore graphs with diameter D ≥ 3 except the (2D + 1)-sided polygons.

B0524984 Sanjeev Gupta

2 Elementary Properties 7

The proof of Theorem 2.2 follows immediately from the elementary property that
for each vertex v counted in ni there is a unique path of length i from a
distinguished vertex u.

B0524984 Sanjeev Gupta

Chapter 3

Diameter 2

The first major result of Hoffman and Singleton [9] concerns a Moore graph X
with degree d and diameter D = 2. This has n = 1 + d + d(d − 1) = d2 + 1 vertices
and girth g = 5. Let A be its adjacency matrix so with an arbitrary numbering of
its vertices

1 if vertices i and j are adjacent
(A)ij = for i, j = 1, 2, ..., n.
0 otherwise

The distance between any pair of vertices is at most 2 since X has diameter 2, and
the shortest path between them is unique as X has girth 5. Thus A is symmetric
with zeros along its diagonal with each row and column adding to d. The 0th, 1st
and 2nd order adjacencies are given by matrices I, A and A2 − dI (we exclude
those paths of length 2 where an arc is retraced) respectively and

A2 − dI + A + I = A2 + A − (d − 1)I = J, (3.1)

the matrix with each entry equal to 1. If u is the column vector whose entries are
all 1, then Ju = nu and Au = du. If v is another non-zero column vector such that
Av = dv then if vi is an entry of v with largest absolute value then (Av)i = dvi and
P0
vj = dvi where the sum is over those d vertices j adjacent to i. By the
maximality of vi we conclude that each vj = vi and continuing in this way, since X
is connected, we further conclude that v is a multiple of u and d has multiplicity 1
as an eigenvalue of A. Furthermore if v is an eigenvector of A with eigenvalue
0 0 0 0 0
λ 6= d, v its transpose, then (v A )u = (Av) u = λv u and
0 0 0 0 0 0 0
(v A )u = v (A u) = v (Au) = dv u, so (d − λ)v u = 0 and hence v is orthogonal to

B0524984 8 Sanjeev Gupta

3 Diameter 2 9

u and Jv = 0. From (3.1) we conclude that λ2 + λ − (d − 1) = 0 and A has at most

2 additional distinct eigenvalues:
√
−1 + 4d − 3
λ1 = ,
√2 (3.2)
−1 − 4d − 3
λ2 = .
2
If λi has multiplicity mi then 1 + m1 + m2 = n = d2 + 1 and d + m1 λ1 + m2 λ2 = 0
√
as the trace(A)=0. Substitution from (3.2) gives (m1 − m2 ) 4d − 3 = d2 − 2d, the
conclusion being that either (i) m1 = m2 and d = 0 or 2, or (ii) 4d − 3 = s2 for
some positive integer s. We discard the case d = 0 as we require a graph with
diameter D = 2. Then the remaining case with d = 2 is the cycle C5 , a Moore
graph of type (2, 2), clearly the only one of that type. When 4d − 3 = s2 we get
(s2 +3)
d + m1 (−1+s)
2
+ (d2 − m1 ) (−1−s)
2
= 0 and substituting d = 4
we get
s5 + s4 + 6s3 − 2s2 + (9 − 32m1 )s = 15. Thus s divides 15 and so s ∈ {1, 3, 5, 15}
and d ∈ {1, 3, 7, 57}. We discard the case d = 1 as there is no such graph with
diameter 2. We tabulate the results below:

Table 3.1: Moore Graphs of Diameter 2

s d λ1 λ2 m1 m2 n
√ √
−1+ 5 −1− 5
- 2 2 2
2 2 5
3 3 1 -2 5 4 10
5 7 2 -3 28 21 50
15 57 7 -8 1729 1520 3250

This concludes the determination of possible degrees d for Moore graphs of

type (d, 2). Hoffman and Singleton [9] go on to prove existence and uniqueness for
Moore graphs of type (3, 2) and (7, 2).

Let X be a Moore graph of type (d, 2). Then n = 1 + d2 . Let u be a distinguished

vertex numbered 0 and its d neighbours at tier 1 numbered 1 to d. For
i ∈ {1, 2, . . . , d} let Si denote the subset of (d − 1) tier 2 vertices adjacent to vertex
i in tier 1 numbered (i(d − 1) + 2) to (i(d − 1) + d) and with this numbering let A

B0524984 Sanjeev Gupta

3 Diameter 2 10

be the adjacency matrix of X. For i, j ∈ {1, 2, . . . , d} let Pij be the (d − 1) × (d − 1)

matrices consisting of the rows of A restricted to the tier 2 vertices in Si , and the
columns of A restricted to the vertices in Sj . Then the d(d − 1) × d(d − 1) lower
right submatrix of A, denoted B, shows the adjacency relations between tier 2
vertices of X through what Hoffman and Singleton [9] call the "re-entering arcs".
They proceed to give further form to B through a series of observations that are
direct consequences of the elementary properties of Chapter 2 and thereby show
uniqueness of Moore graphs of type (3,2) and (7,2) by showing that the adjacency
matrices are uniquely defined with an appropriate numbering of the vertices.

Observation 3.1. The graph contains no cycle of length less than 5.

We have already noted that an equivalent definition of a Moore graph of diameter

D is that it has girth g = 2D + 1.

Observation 3.2. The diagonal blocks of B, denoted Pii , are 0.

If v and w are adjacent vertices in Si then together with vertex i in tier 1 they
form a 3-cycle contradicting Observation 3.1.

Observation 3.3. The blocks Pij for i 6= j of B are permutation matrices.

If a ∈ Si and b, c ∈ Sj are distinct vertices with a adjacent to both b and c, then

a, b, c and vertex j in tier 1 would form a 4-cycle, again contradicting
Observation 3.1. Since each vertex a ∈ Si in tier 2 is adjacent to exactly (d − 1)
vertices in tier 2 and there are exactly (d − 1) subsets Sj with i 6= j each Pij has
one 1 in each row and column.

Observation 3.4. The vertices may be numbered such that P1i = Pi1 = I (i 6= 1).

Whatever the order of the vertices in S1 we can renumber the vertices within each
Si such that they are in the same order as their unique adjacent vertex in S1 .
Then P1i = I and hence Pi1 = I.

B0524984 Sanjeev Gupta

3.1 Uniqueness of the Moore graph of type (3,2) 11

If vertices are relabelled according to Observation 3.4 we say that A is in canonical

form and we deduce

Proposition 3.5. With A in canonical form

d
X
Pij = J for j 6= 1; and (3.3)
i=1
d
X
Pik + Pij Pjk = J for i 6= k. (3.4)
j=1

Proof. Evaluating (3.1) using the canonical form for A and restricting the results
to the lower right d(d − 1) × d(d − 1) submatrix we see that the A2 term gives
B 2 + K, where K is the d × d array of diagonal (d − 1) × (d − 1) blocks J. Thus B
satisfies B 2 + B − (d − 1)I = J − K. For i 6= k the matrices I and K contribute 0
to the (i, k)-th block of B and hence (3.4) follows. When j = 1 in (3.3) the sum is
(d − 1)I where I is the (d − 1) × (d − 1) identity matrix by the given construction.
When j 6= 1 the sum consists of (d − 1) permutation matrices each containing
(d − 1) ones. If any (x, y)-th coordinate in the sum were greater than 1 we would
require, for some distinct h and i, (Phj )xy = (Pij )xy = 1. But this would imply that
the x-th vertices in both Sh and Si are adjacent to the y-th vertex in Sj . Since
j 6= 1 the x-th vertices would also be adjacent to the x-th vertex of S1 by the
construction and these vertices would form a 4-cycle contradicting Observation 3.1.
Hence no coordinate in the sum can be greater than 1 and since there are exactly
(d − 1)2 ones in total in the sum and it has (d − 1)2 coordinates the sum is J as
required.

3.1 Uniqueness of the Moore graph of type (3,2)

We are now able to prove

Theorem 3.6. The Moore graph of type (3, 2) is unique.

Proof. With d = 3 and A in canonical form B is a 3 × 3 array of 2 × 2 matrices:

B0524984 Sanjeev Gupta

3.1 Uniqueness of the Moore graph of type (3,2) 12

 
0 I I
 
B=
 I 0 P 

0
I P 0

0
with P a 2 × 2 permutation matrix and P its transpose. If P = I then by (3.3)
with j = 3 we would have 2I = J, a contradiction. Hence
" #
0 1
P =
1 0

the only other 2 × 2 permutation matrix. Thus B and hence A is uniquely defined
and the graph exists and is unique subject to a suitable numbering of its
vertices.

The unique Moore graph of type (3, 2) is the Petersen graph shown below in its
symmetric form and with a partition into tiers.

0
2
1 3
4 8 1 2 3

7 6 4 5 6 7 8 9

5 9

Figure 3.1: The Petersen Graph

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 13

3.2 Uniqueness of the Moore graph of type (7,2)

Hoffman and Singleton [9] continue by examining the submatrix B of a Moore

graph of type (7, 2). With A in canonical form its first 8 rows are

0 11 . . . 1 00 . . . 0 00 . . . 0 . . . 00 . . . 0
1 00 . . . 0 11 . . . 1 00 . . . 0 . . . 00 . . . 0
1 00 . . . 0 00 . . . 0 11 . . . 1 . . . 00 . . . 0
.. .. .. .. .. ..
. . . . . .
1 00 . . . 0 00 . . . 0 00 . . . 0 . . . 11 . . . 1

and
 
0 I ... I
 
I 0 . . . P27 
B = .
 
 .. .. .. .. 
 . . .  
I P72 ... 0

where the Pij are 6 × 6 permutation matrices satisfying the equations of

Proposition 3.5. They show that by an appropriate numbering of the vertices the
adjacency matrix of any Moore graph of type (7, 2) is uniquely defined and hence
there is only one such graph. They begin with a detailed analysis of submatrices of
A.

Lemma 3.7. The principal submatrix of A, the adjacency matrix of a Moore

graph of type (7, 2), given by

 
0 I I
 
M =
 I 0 P 

0
I P 0

has eigenvalue 2 with multiplicity at least 3.

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 14

Proof. Here M is the upper left principal submatrix of B with P = P23 . We noted
in Chapter 3 that A has eigenvalue 2 with multiplicity 28. By direct calculation we
exhibit 7 of its linearly independent eigenvectors, writing out the first 8
components and representing the remaining 42 components with 7 vectors of
dimension 6:
0 0 0 0 0 0 0 0
x1 = [ −14 −4 −4 −4 −4 −4 −4 −4 u u u u u u u]
0 0 0 0 0 0 0 0
x2 = [ 0 3 −3 0 0 0 0 0 u −u 0 0 0 0 0]
0 0 0 0 0 0 0 0
x3 = [ 0 0 3 −3 0 0 0 0 0 u −u 0 0 0 0]
0 0 0 0 0 0 0 0
x4 = [ 0 0 0 3 −3 0 0 0 0 0 u −u 0 0 0]
0 0 0 0 0 0 0 0
x5 = [ 0 0 0 0 3 −3 0 0 0 0 0 u −u 0 0]
0 0 0 0 0 0 0 0
x6 = [ 0 0 0 0 0 3 −3 0 0 0 0 0 u −u 0]
0 0 0 0 0 0 0 0
x7 = [ 0 0 0 0 0 0 3 −3 0 0 0 0 0 u −u ]

If x8 is another linearly independent eigenvector with eigenvalue 2 then we may

assume its first 7 components are zero as we can eliminate nonzero components
with a linear combination of eigenvectors x1 , . . . , x7 . Furthermore if the eighth
component of x8 is nonzero then the first component of Ax8 is also nonzero
contradicting our assumption that the first component of x8 is zero. Hence we may
assume that the first 8 components of x8 are zero and so each of the remaining 21
linearly independent eigenvectors of A have zeros in their first 8 components and
their last 42 components are eigenvectors of B with eigenvalue 2.

Let
0 0 0 0 0 0 0 0
v = [ 0 0 0 0 0 0 0 0 v1 v2 v3 v4 v5 v6 v7 ]

be such an eigenvector. Since the last 42 components of x1 are an eigenvector of B

0
with eigenvalue 6 we can deduce that u vi = 0 for each i because as eigenvectors of
B they correspond to different eigenvalues, cf. Chapter 3. Now consider the upper
left principal 26 × 26 submatrix L of A having M as its lower right
18 × 18 submatrix, and the 27 × 27 submatrix L∗ obtained by augmenting L with
one column and the corresponding row of length 27 taken from an unspecified
member of the fourth block; symbolically we have

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 15

0 0 0
L∗ = L + [ 0 0 0 0 1 0 0 0 eh ei ej 0 ]0

where ei is the column vector with 1 in the i-th coordinate and zeros elsewhere and
h, i and j are distinct; this column corresponds to the h-th vertex in S4 . If we let
E2 , EL and EL∗ represent the eigenspace for eigenvalue 2 of A and those
corresponding to L and L∗ then by Theorem 27.15 of [13] we have
dim (E2 + EL ) + dim (E2 ∩ EL ) = dim (E2 ) + dim (EL ) and hence a subspace of E2
of size at least 28 + 26 − 50 = 4 lies in EL and at least 5 in EL∗ . Inspection of
eigenvectors x1 , . . . , x7 and v of A gives a basis for the 4-space:
0 0 0 0 0 0 0 0
y1 = [ −14 8 −4 −4 −7 −7 −7 −7 5u u u 0 0 0 0 ]
0 0 0 0 0 0 0 0
y2 = [ 0 3 −3 0 0 0 0 0 u −u 0 0 0 0 0 ]
0 0 0 0 0 0 0 0
y3 = [ 0 0 3 −3 0 0 0 0 0 u −u 0 0 0 0 ]
0 0 0 0 0 0 0 0
y4 = [ 0 0 0 0 0 0 0 0 v1 v2 v3 0 0 0 0 ]
0
for some vi where u vi = 0, y2 = x2 , y3 = x3 and y4 must be a linear combination of
the eigenvectors of the form v above as otherwise one of the last four blocks would
be proportional to u. Since these are eigenvectors of A they are eigenvectors of L∗ .
If w is a fifth basis vector for the 5-space then it too cannot be a linear
combination of the xi and thus has the form
0 0 0 0 0 0 0 0
w = [ 0 0 0 0 0 0 0 0 w1 w2 w3 w4 0 0 0 ]

with components 1 to 8 and 28 to 50 being zero for w to lie in the eigenspace of

0
L∗ . Hence w4 has at most 1 nonzero component and since u wi = 0 we must have
w4 = 0. Then y4 and w are 2 independent eigenvectors for M with eigenvalue 2 as
both have zeros in the components not corresponding to M and by inspection the
0 0 0 0
column vector (u u u ) also has eigenvalue 2 for M and all three are linearly
independent. Hence eigenvalue 2 of M has multiplicity at least 3.

Remarkably this observation is enough to show the following result which together
with another series of observations is used to prove the existence and uniqueness of
the Moore graph of type (7, 2):
Lemma 3.8. With A in canonical form all Pij for distinct i, j 6= 1 are involutions.

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 16

Proof. With M as above let v be an eigenvector with eigenvalue 2 where

0 0 0 0
v = (x y z ) and each x, y, z is a column vector of length 6. Then

y + z = 2x
x + Pz = 2y
0
x + P y = 2z

and eliminating x from the last two equations gives

" #" # " #
0 (I + 2P ) y y
0
=3 .
(I + 2P ) 0 z z

Thus the multiplicity

" of 2 as an eigenvalue
# of M equals the multiplicity of 3 as an
0 (I + 2P )
eigenvalue of 0
.
(I + 2P ) 0
" #
0 T
Given a real square matrix R of the form R = 0
we have
T 0
0
det(λI − R) = det(λ2 I − T T ) and hence R has as its eigenvalues the square roots
0
of the eigenvalues of T T and their negatives. Thus we deduce that the multiplicity
of 2 as an eigenvalue of M is the multiplicity of 9 as an eigenvalue of
0 0
(I + 2P )(I + 2P ) = 5I + 2(P + P ). Thus the multiplicity of 2 as an eigenvalue of
0
M is equal to the multiplicity of 2 as an eigenvalue of P + P ; since P is a
permutation matrix this is the number of disjoint cycles in P . Hence P is
composed of at least 3 disjoint cycles by Lemma 3.7 and by (3.3) of Proposition 3.5
is composed of precisely 3 disjoint cycles (as otherwise P and I would have
nonzero entries at the same coordinates) and is an involution. Proposition 3.5 then
gives the required result for all non-diagonal blocks Pij with i, j 6= 1.

Since this Lemma shows that all Pij are symmetric it leads to

Corollary 3.9. In a Moore graph of type (7, 2) in canonical form

Pij Pjk Pki = Pjk if i 6= j, i 6= k, and j, k 6= 1.

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 17

Proof. If i = 1 the result follows from Observation 3.4. With i 6= 1 let the
involution Pij = (ab)(cd)(ef ). Then Proposition 3.5 implies that the companion of
0
a in Pjk = Pkj = Pkj comes from one of (cd) or (ef ) and that of b comes from the
other. Hence we may assume Pjk = (ac)(be)(df ) and Pij Pjk = (aed)(bcf ). Since Pik
lies in a row with Pij and a column with Pjk Proposition 3.5 implies that
Pik = (af )(bd)(ce) since it cannot share a substitution of terms appearing in
Pij , Pjk or Pij Pjk and evaluating the product Pij Pjk Pki gives the result.

If all the i, j, k are distinct multiplying the above on the left by Pjk and on the
right by Pik we have

Corollary 3.10. Pjk Pji Pjk = Pik if i, j, k are distinct and j, k 6= 1.

Corollary 3.11. If i, j, k, l are distinct Pij 6= Pkl .

Proof. If any of i, j, k, l equals 1 then the result follows by the canonical

construction and Proposition 3.5. Assume then that P23 = P45 for a contradiction.
Then P23 P34 P45 = P32 P34 P32 = P42 = P24 by Corollary 3.10 and also
P23 P34 P45 = P45 P43 P45 = P35 so P24 = P35 . Since P32 P34 P32 = P24
P34 = P45 P24 P45 = P25 . Then P23 + P24 + P25 = P32 + P34 + P35 = P42 + P43 + P45
and Proposition 3.5 implies that P26 + P27 = P36 + P37 = P46 + P47 . But this
contradicts Proposition 3.5 as we would then have P36 = P27 and P27 = P46 . It is
clear that the argument can be extended to the general case.

Finally Hoffman and Singleton [9] are in a position to prove

Theorem 3.12. The Moore graph of type (7, 2) is unique.

Proof. In canonical form the submatrix B of a Moore graph of type (7, 2) is a

7 × 7 array of 6 × 6 matrices. By Corollary 3.11 there are 15 distinct involutions
Pij with 2 ≤ i < j ≤ 7; in addition given any 6 elements there are precisely 15
distinct involutions with 3 disjoint cycles and no fixed points. Hence the involution
Pij represented by (12)(34)(56) appears once and by renumbering the vertices of

B0524984 Sanjeev Gupta

3.2 Uniqueness of the Moore graph of type (7,2) 18

tier 1 can be brought to the P23 position. Similarly by renumbering vertices

4, 5, 6, 7 of tier 1 we may assume that P24 is either (13)(25)(46) or (13)(26)(45).
Finally by renumbering the fifth and sixth vertices of S1 if needed we can assume
P24 = (13)(25)(46). An argument similar to Corollary 3.9 uniquely determines the
remaining 3 involutions P2j and Corollary 3.10 with j = 2 gives the other Pik .
Hence the adjacency matrix of any Moore graph of type (7, 2) can be uniquely
determined by a suitable numbering of the vertices.

B0524984 Sanjeev Gupta

Chapter 4

Properties of Moore graphs of

type (57, 2)

Hoffman and Singleton [9] do not go into a discussion on Moore graphs of

type (57, 2) other than stating these are the only other possible Moore graphs with
diameter D = 2. Here we consider some combinatorial properties of such a graph,
n×57
if it indeed exists. It has n = 572 + 1 = 3250 vertices, e = 2
= 92625 edges,
g = 5 girth, is regular and distance-regular and we mentioned that Higman showed
it cannot be vertex-transitive, Mačaj and Širáň [10] showing that the order of its
automorphism group is in fact bounded by 375. Its adjacency matrix A has
eigenvalues 57, 7 and −8 with multiplicities 1, 1729 and 1520, respectively.

4.1 Counting Cycles

The simplest properties apply to all Moore graphs so let X be a Moore graph of
type (d, D). Then:

X has u = 12 d (d − 1)D distinct (2D + 1)-cycles through any given vertex.

Take any vertex as the distinguished vertex. Since X has girth g = 2D + 1
any cycle of length 2D + 1 must contain precisely 1 edge in tier D and each
such edge determines a unique (2D + 1)-cycle through the distinguished
vertex. Since there are d (d − 1)D−1 vertices in tier D each connected to d − 1

B0524984 19 Sanjeev Gupta

4.1 Counting Cycles 20

other vertices of tier D the result follows.

Thus a Moore graph of type (57, 2) has 89376 distinct 5-cycles through every
vertex.

u·n
X has A = 2D+1
distinct (2D + 1)-cycles.
Clearly u · n counts the total number of (2D + 1)-cycles in X and each cycle
is counted 2D + 1 times.

Thus a Moore graph of type (57, 2) has 58094400 distinct 5-cycles.

X has v = u · (d − 2) distinct (2D + 2)-cycles through any given vertex.

Any cycle of length 2D + 2 must contain precisely 2 adjacent edges in tier D
and each such pair determines a unique (2D + 2)-cycle from the outer
vertices of the pair through the distinguished vertex. There are u edges in
tier D and we can chose an adjacent edge from either vertex of each edge in
d − 2 ways. This counts the adjacent pairs twice and hence the result follows.

Thus a Moore graph of type (57, 2) has 4915680 distinct 6-cycles through every
vertex.

v·n
X has B = 2D+2
distinct (2D + 2)-cycles.
Clearly v · n counts the total number of (2D + 2)-cycles in X and each cycle
is counted 2D + 2 times.

Thus a Moore graph of type (57, 2) has 2662660000 distinct 6-cycles.

Friedman [6] in 1969 used these counting arguments and computer programs to
show the impossibility of certain Moore graphs by checking whether A and B are
integers but his results do not extend those of Hoffman and Singleton [9] for D = 2
or D = 3. He asked the question whether these counting methods could be
extended to cycles of greater length. In 1973 Plesník [11] was able to show that

B0524984 Sanjeev Gupta

4.2 Independent Set 21

each edge of a Moore graph of type (d, D) is contained in the same number rm of
cycles of length m where m ≤ 4D + 1. He provided a recurrence relation for rm
from which we can easily deduce that each vertex is contained in 12 drm cycles of
length m. This extended the results of Friedman [6] but does not settle the
problem of Moore graphs of type (57, 2), although we are now able to calculate the
number of cycles of lengths 5 to 9 through a given vertex of such a graph:

Cycle Length Number of Cycles

5 89376
6 4915680
7 265446720
8 14874847680
9 833252001120

4.2 Independent Set

We can use counting arguments to investigate the largest size of an independent

set C in a Moore graph X of type (d, 2), cf. Godsil and Royle [8] p. 92. Let
|C| = c and assume the n vertices are labelled so that the vertices {1, 2, . . . , n − c}
are the ones not in C. If i is a vertex not in C and ki is the number of its
neighbours in C then since no two vertices in C are adjacent
n−c
X
dc = ki .
i=1

In addition since any two nonadjacent vertices in X have a unique common

neighbour
  X n−c  
c ki
= .
2 i=1
2

Hence for any real µ we have

n−c
X
(ki − µ)2 = (n − c)µ2 − 2µdc + c2 + c(d − 1) (4.1)
i=1

B0524984 Sanjeev Gupta

4.2 Independent Set 22

and since this is nonnegative the discriminant

4d2 c2 − 4c(n − c)(c + d − 1) = 4c(c2 + c(d − 2) − (d2 + 1)(d − 1)) ≤ 0.

Solving the quadratic in c gives an upper bound for the size of the independent set
C. If we let c equal this upper bound then (4.1) gives a quadratic in µ and putting
µ equal to the positive integer root (if any) we deduce that ki = µ and hence each
vertex not in C is adjacent to a fixed number of vertices in C. Thus we have the
following results:

Degree Independent Set Size ki

3 ≤4 2
7 ≤ 15 3
57 ≤ 400 8

Hence if a Moore graph of type (57, 2) exists then it has an independent set C of
size at most 400 and if such a set of size 400 exists then each of the 2850 vertices
not in it is adjacent to 8 vertices in C.

Godsil and Royle [8] p. 93 give a construction of the Hoffman-Singleton graph, the
Moore graph of type (7, 2), based on the assumption that it has an independent set
of size 15. The construction is related to the projective geometry P G(3, 2) of
dimension three over GF (2). Their construction identifies an independent set of
size 15. Applying their methodology to the Moore graph of type (57, 2) we note
that if V is a vector space of dimension 4 over the field F with order 7 then the
projective space P G(3, 7) is the system of 1-, 2- and 3-dimensional subspaces of V ,
referred to as the points, lines and planes respectively of P G(3, 7). Since V has
74 − 1 nonzero vectors and each 1-dimensional subspace has 7 − 1 nonzero vectors
we conclude that there are (74 − 1)/(7 − 1) = 400 points. Each 2-dimensional
subspace contains 72 − 1 nonzero vectors and hence each line contains 7 + 1 = 8
400·399
points. Since 2 points define a line containing 8 points there are 8·7
= 2850
lines. Hence a possible construction of a Moore graph of type (57, 2) could be
attempted by using the 400 points of P G(3, 7) as the independent set C; the

B0524984 Sanjeev Gupta

4.3 Vertex-Intransitivity 23

remaining 2850 vertices would be represented by the lines of P G(3, 7) with each
line being adjacent to 8 points within C and 57 − 8 = 49 other lines. We would
2850·49
then have 2
+ 2850 · 8 = 92625 edges as is required for a Moore graph of
type (57, 2). We are still no closer to defining a suitable adjacency relation
between the lines of P G(3, 7).

4.3 Vertex-Intransitivity

In the final section of this chapter we show using a method of Higman,

cf. Godsil [7], that if a Moore graph of type (57, 2) exists then it is not
vertex-transitive. As mentioned before Mačaj and Širáň [10] have shown that in
fact the automorphism group of such a graph has order at most 375, a size much
lower than the 3250 vertices of such a graph.

4.3.1 Feasibility Condition for Automorphisms

We begin with some preliminary results on the real symmetric n × n matrix

A = (aij ) with ev(A) the set of its distinct eigenvalues. Rn has an orthonormal
basis consisting of eigenvectors of A and there is an orthogonal matrix L and a
0
diagonal matrix D such that LAL = D (Godsil and Royle [8] p. 170). We take L
to be the matrix whose rows are an orthonormal basis of eigenvectors of A and D
0
is the diagonal matrix of eigenvalues of A. Then since A = L DL it follows that
0
X
A= θL Iθ L
θ∈ev(A)

where Iθ is the diagonal matrix with nonzero entries equal to 1 at coordinates

corresponding to eigenvalue θ in D, so
X
D= θIθ .
θ∈ev(A)
0
Let Eθ = L Iθ L so that
X X
Eθ = I and A = θEθ , the co-called spectral decomposition of A.
θ∈ev(A) θ∈ev(A)

B0524984 Sanjeev Gupta

4.3 Vertex-Intransitivity 24

0
Then Eθ2 = Eθ and Eθ = Eθ so the matrix Eθ is an orthogonal projection. If θ, τ
are distinct eigenvalues then Eθ Eτ = 0 as Iθ Iτ = 0. Applying this to the spectral
decomposition of A we have AEθ = θEθ and it follows that Eθ is the orthogonal
projection onto the eigenspace of A associated with the eigenvalue θ. As Eθ is
symmetric and Eθ2 = Eθ its eigenvalues are 0 or 1 and the trace(Eθ ) is equal to its
rank which is the dimension of the eigenspace associated with θ and so the
trace(Eθ ) is the multiplicity of the eigenvalue θ.
Using the spectral decomposition of A and recalling that Eθ Eτ = 0 for distinct
X
eigenvalues θ, τ we note that if p(x) is any polynomial then p(A) = p(θ)Eθ .
θ∈ev(A)
Since we may choose p(x) to vanish at all but one of the eigenvalues of A it follows
that Eθ is a polynomial in A. Indeed, applying the results of Chapter 3 on Moore
graphs of type (d, 2) with adjacency matrix A and ev(A)={d, λ1 , λ2 } taking
(x − λ1 )(x − λ2 )
pd (x) =
(d − λ1 )(d − λ2 )
(x − d)(x − λ2 )
pλ1 (x) =
(λ1 − d)(λ1 − λ2 )
(x − d)(x − λ1 )
pλ2 (x) =
(λ2 − d)(λ2 − λ1 )
we have Eθ = pθ (A) for each θ ∈ ev(A) and using (3.1) this can be simplified to
give Eθ in terms of the matrices I, J and A. Following this process through for a
Moore graph of type (57, 2) with θ = λ1 = 7 we have
(A − 57I)(A + 8I) 50A + 400I − J
E7 = = (4.2)
(7 − 57)(7 + 8) 750
a result we require later.
To continue with the search for a feasibility condition we note that an
automorphism π of a graph X with adjacency matrix A can be identified with a
0
permutation matrix P such that P = P −1 . As aij is the (i, j)-th component of A,
0
the (i, j)-th component of P AP is given by aπ(i)π(j) and, since π is an
automorphism of X, i is adjacent to j if and only if π(i) is adjacent to π(j) and
0
hence A = P AP or AP = P A. Thus the permutation matrix P commutes with A
and, since Eθ = pθ (A), P commutes with each projection Eθ . This implies that P

B0524984 Sanjeev Gupta

4.3 Vertex-Intransitivity 25

leaves invariant the eigenspace associated with eigenvalue θ. In general if a matrix

P leaves a subspace U of Rn invariant then it determines a linear mapping on U .
We call the trace of this linear mapping the trace of P restricted to U , denoted by
trU (P ), and note that it is a sum of eigenvalues of P .

Lemma 4.1. Let X be a simple graph, P a permutation matrix representing an

automorphism of X, U an eigenspace of the adjacency matrix of X, and E the
orthogonal projection on U . Then trU (P ) = tr(P E) and is an algebraic integer.

Proof. As the automorphism group of X is finite there is a least positive integer m

such that P m = I and hence the eigenvalues of P are zeros of the monic
polynomial xm − 1 and it follows that trU (P ) is an algebraic integer.
If u1 , . . . , un is an orthonormal basis for Rn with u1 , . . . , um being an orthonormal
basis for U then
m m n
0 0 0
X X X
trU (P ) = ui P ui = (Eui ) P (Eui ) = ui EP (Eui )
i=1 i=1 i=1

as Euj = 0 for j > m and hence we conclude that

trU (P ) = tr(EP E) = tr(P EE) = tr(P E)

as E 2 = E.

Thus we have the desired feasibility condition for automorphisms of X. Applying

this to (4.2) we see that if an automorphism π of a possible Moore graph of
type (57, 2) is represented by a permutation matrix P = (pij ) then the trace of P
restricted to the eigenspace U of eigenvalue 7 is given by
50tr(P A) + 400tr(P ) − tr(P J)
trU (P ) = tr(P E7 ) = (4.3)
750
and this must be an algebraic integer. Since P is a permutation matrix it is
immediate that tr(P J) = n = 3250. Also it is immediate that tr(P ) is the number
of vertices fixed by the automorphism π. Finally tr(P A) gives the number of
P
vertices mapped to an adjacent vertex by π since (P A)ii = k pik aki and pik = 1 if

B0524984 Sanjeev Gupta

4.3 Vertex-Intransitivity 26

and only if k = π(i) and it is clear that aπ(i)i = 1 if and only if vertex i is adjacent
to vertex π(i).
We now have a necessary condition for the existence of certain automorphisms of a
simple graph. Higman proceeds by analysing in detail a possible automorphism of
order 2 of such a graph.

Theorem 4.2. (Higman) There is no vertex-transitive Moore graph of type (57, 2).

Proof. Aiming for a contradiction, suppose that X is a Moore graph of type (57, 2)
with adjacency matrix A and a vertex-transitive automorphism group denoted by
Aut(X). Then by the orbit-stabiliser lemma (Godsil and Royle [8] p. 21) n = 3250
divides the order of Aut(X) which is therefore even. Thus Aut(X) contains an
involution. Let π be such an automorphism of order 2, P the permutation matrix
corresponding to π, F = fix(π) the set of vertices fixed by π and Y the subgraph of
X induced by F .
If two non-adjacent vertices are fixed by π then they have the same number of
adjacent vertices fixed by π, the unique common vertex being one. Thus there are
two possible cases. Either Y is a star, each fixed vertex being at distance at most
one from a fixed vertex, or Y is a connected graph of diameter 2 and girth 5 and is
thus a Moore graph with 5, 10 or 50 vertices. Since a star in X can have at most
d + 1 = 57 + 1 = 58 vertices |F | ≤ 58 and hence tr(P ) ≤ 58.
Now suppose that π does not interchange the endpoints of any edge in X so that,
as we have noted above, tr(P A) = 0. Then π either fixes a vertex or swaps it with
a vertex at distance 2. If we let A denote the adjacency matrix of the complement
X of the Moore graph X of type (57, 2) then we note that since there is a unique
path of length 2 between non-adjacent vertices of X we have
A = A2 − 57I = J − I − A by (3.1) and if A = (aij ) then aij = 1 precisely when
vertices i and j are at distance 2 in X and aij = 0 otherwise. Thus we have
tr(P ) + tr(P A) = 3250. Moreover if π(u) 6= u then π fixes the unique common
neighbour v of u and π(u). For each such v there can be at most 56 such vertices u
and so we also have the inequality tr(P A) ≤ 56tr(P ). Together these equations
imply that tr(P ) ≥ 58 and hence we have the equality tr(P ) = 58. In this case (4.3)

B0524984 Sanjeev Gupta

4.3 Vertex-Intransitivity 27

implies that the trace of P restricted to the eigenspace corresponding to eigenvalue

400·58−3250 133
7 is 750
= 5
which is not an algebraic integer contradicting Lemma 4.1.
We may conclude that π interchanges the vertices of some edge e = uv in X. Then
π swaps the remaining 56 vertices adjacent to u with the remaining 56 vertices
adjacent to v resulting in 56 paths of length 3 each of which is fixed by π. Since X
has girth 5 each path of length 3 lies in a unique 5-cycle and thus determines a
unique vertex at distance 2 from both u and v. Since this vertex is fixed by π we
have a set S of size at least 56 of vertices fixed by π. But any vertex at distance 2
from both u and v not in S determines a path of length 3 on uv that is not fixed
by π and so is not a fixed vertex of π. Thus S has exactly 56 fixed vertices.
We may conclude that π must swap the vertices of some edge and have precisely
3250−56
56 fixed vertices. Hence it is a permutation with 2
= 1597 transpositions and
is thus an odd permutation.
Higman nows concludes with the contradiction we seek. Let G = Aut(X) and let u
be a vertex of X that is fixed by the involution π. Then by the orbit-stabiliser
lemma |G| = |Gu | · |uG | = 3250 · |Gu |, and since u is fixed by π and is of order 2,
|Gu | is even and thus |G| is divisible by 4. Then if H is the intersection of G and
the alternating group A3250 , since exactly half the elements of G are even
permutations, |H| is also even and hence contains an involution, a contradiction as
we have seen that such involutions are necessarily odd permutations.

B0524984 Sanjeev Gupta

Chapter 5

Diameter 3

Hoffman and Singleton [9] conclude their paper with an analysis of Moore graphs
with diameter D = 3.

Theorem 5.1. If the polynomial which is characteristic of Moore graphs of type

(d, D), D ≥ 2, is irreducible in the field of rational numbers, then no such graphs
exist unless d = 2.

Define polynomials Fi (x) recursively as follows:

F0 (x) = 1
F1 (x) = x + 1
Fi+1 (x) = xFi (x) − (d − 1)Fi−1 (x)

If A is the adjacency matrix of a Moore graph X of type (d, D) then FD (A) = J.

Indeed by a straightforward induction argument the (i, j)-th entry of Fm (A) is 1 if
there is a path of length not greater than m from vertex i to vertex j and zero
otherwise. A has eigenvalue d with multiplicity one and if λ is another eigenvalue
different from d then arguing as in Chapter 3 λ is a root of FD (x), which being
irreducible over Q, must divide the characteristic polynomial of A. Hence a root of
FD (x) is an eigenvalue of A. Let λ1 , . . . , λD be the roots of FD (x). Since the
coefficients of xD and xD−1 in FD (x) are one, D
P
i=1 λi = −1. By the irreducibility
of FD (x) its roots have equal multiplicity, m say, as eigenvalues of A and since X
d(d−1)D −2
has n = vertices if d > 2,
d−2

d (d − 1)D − 1
 
n−1
m= = .
D D d−2

B0524984 28 Sanjeev Gupta

5 Diameter 3 29

As the trace of A is zero we also have

D
X
d+m λi = 0
i=1

and hence m = d and substituting for m we conclude that

(d − 1)D − D(d − 1) + (D − 1) = 0.

As a polynomial in (d − 1), as D ≥ 2, by Descartes’ rule of signs this equation has

at most 2 positive roots. Since d = 2 is a double root no d > 2 satisfies the
polynomial and thus the theorem follows. When d = 2 we have the (2D + 1)-gon a
Moore graph of type (2, D).

When D = 3 we have the polynomial F3 (x) = x3 + x2 − 2(d − 1)x − (d − 1).

Suppose a Moore graph of type (d, 3) exists with d > 2. Then by the above
theorem we have at least one integer root r of F3 (x) = 0. Thus

r2 (r + 1)
d−1= .
2r + 1
But 2r + 1 is relatively prime to both r and r + 1 and so for integer d we require
2r + 1 = ±1. In either case we have d = 1 - a contradiction. Hence the only Moore
graph with diameter D = 3 is the Moore graph of type (2, 3).

B0524984 Sanjeev Gupta

Chapter 6

Convex Cycles

In this chapter we consider a characterisation of Moore graphs based on the 2012

paper by Azarija and Klavžar [1].
Given a simple graph X we denote by V (X) its vertex set and by E(X) its edge
set.

Definition 6.1. A subgraph Y of a simple graph X is convex if for any

u, v ∈ V (Y ) every shortest uv-path lies entirely in Y .

Thus if Y is convex in X then for any u, v ∈ V (Y ) we have dY (u, v) = dX (u, v)

where dX denotes the shortest path length in X.
Let ρ(X) denote the number of convex cycles in a simple graph X with n vertices,
e edges and girth 3 ≤ g ≤ n. Azarija and Klavžar [1] prove
n
Theorem 6.2. ρ(X) ≤ g
(e − n + 1) with equality holding if and only if X is an
even cycle or a Moore graph

thus providing a new characterisation of Moore graphs. They begin by

characterising convex cycles in X.

Lemma 6.3. Let C be a cycle in X.

If |C| = 2k + 1, k ≥ 1, then C is convex if and only if for every f = xy ∈ E(C)
there is a unique v ∈ V (C) such that

(i) dX (x, v) = dX (v, y) = k, and

(ii) the xv-path (resp. vy-path) in C of length k is the unique shortest xv-path
(resp. vy-path) in X.

B0524984 30 Sanjeev Gupta

6 Convex Cycles 31

If |C| = 2k, k ≥ 2, then C is convex if and only if for every u ∈ V (C) there is a
v ∈ V (C) such that

(iii) dX (u, v) = k, and

(iv) there are exactly two uv-paths in X of length k.

Proof. If C is a convex cycle of length 2k + 1 then given any edge f = xy ∈ E(C)

there is a unique vertex v in C at length k from x (and similarly y) and there can
be no other paths of equal or shorter length in X between x and v (and similarly y
and v) by convexity of C and so conditions (i) and (ii) follow.
Conversely any two p, q ∈ V (C) lie on at least one path of length k in C and this
defines at least one edge f and vertex v of the lemma. p, q cannot be connected by
another path of equal length in X, otherwise uniqueness would be violated in
condition (ii), or a path of shorter length in X, otherwise condition (i) would be
violated. Hence C is convex.
If C is a convex cycle of length 2k then given any u ∈ V (C) there is a unique
v ∈ V (C) connected by two paths in C of length k and by convexity there are no
other paths of equal or shorter length in X connecting u and v. Thus
conditions (iii) and (iv) follow.
Conversely assume the conditions hold and for a contradiction suppose there are
vertices p, q in C with a shortest pq-path P not entirely in C. By condition (iii)
0 0
there is a p ∈ V (C) with dX (p, p ) = k and by condition (iv) there are exactly two
0
pp -paths, P1 and P2 say, in X of length k. As C is a cycle of length 2k and
0 0
dX (p, p ) = k the pqp -path in C is of length k, as it cannot be less or greater than
k by condition (iii), hence q lies on one of P1 or P2 , say P1 . If P is shorter than the
pq-subpath of P1 then condition (iii) is violated and if it is of the same length then
condition (iv) is violated. Hence C is convex.

Azarija and Klavžar [1] note that from the first part of Lemma 6.3 we may
conclude that in a graph of girth g = 2D + 1, where D is the diameter of the
graph, all its g-cycles are convex as conditions (i) and (ii) are always satisfied in

B0524984 Sanjeev Gupta

6.1 Odd Convex Cycles 32

this case. Also we note that from the proof of sufficiency in the second part of
Lemma 6.3 we may infer that if the two conditions hold then u and v are antipodal
vertices in the cycle C since condition (iii) implies that dC (u, v) ≥ dX (u, v) = k as
C is a subgraph of X and clearly dC (u, v) ≤ k as C is a 2k-cycle. Then the two
unique uv-paths in X of condition (iv) are the two uv-paths in C that make up C.
As in Azarija and Klavžar [1] we call (f, v) ∈ E(X) × V (X) satisfying conditions
(i) and (ii) of Lemma 6.3 an odd antipodal pair and (u, v) ∈ V (X) × V (X)
satisfying conditions (iii) and (iv) an even antipodal pair.
They now consider odd and even convex cycles separately and finally combine the
results to prove Theorem 6.2.

6.1 Odd Convex Cycles

Using a breadth-first search algorithm from a distinguished vertex u in a simple

graph X we can create a spanning tree T of X. The algorithm begins at u and
connects all neighbouring vertices, called the tier 1 vertices. For each tier 1 vertex
we connect all neighbouring vertices that have not already been reached. We
continue in this way. All vertices of X are eventually reached and the algorithm
stops for the simple graphs we are considering. Azarija and Klavžar [1] use this
construction in

Lemma 6.4. For any u ∈ V (X) there are at most e − n + 1 edges f such that
(f, u) is an odd antipodal pair.

Proof. Let T be a breadth-first search tree of X with distinguished vertex u. Then

if f ∈ E(T ) it is clear that one vertex of f will be closer to u than the other and
hence (f, u) cannot be an odd antipodal pair, condition (i) being violated. As X
has n vertices the minimum number of such f ∈ E(T ) is n − 1 and hence an upper
bound for the number of odd antipodal pairs is e − n + 1.

Let ρo (X) denote the number of odd convex cycles in X. Lemma 6.3 implies that

B0524984 Sanjeev Gupta

6.1 Odd Convex Cycles 33

each odd convex cycle is determined by any one of its odd antipodal pairs and so
we count how many such pairs are possible to determine an upper bound for ρo (X).
We provide a proof different than that of Azarija and Klavžar [1] for the following

n
Lemma 6.5. ρo (X) ≤ g
(e − n + 1) .

Proof. There are n vertices in X and by Lemma 6.4 each vertex has at most
e − n + 1 edges with which to form an odd antipodal pair. Each such pair
determines an odd convex cycle C and each such cycle is counted |C| ≥ g times.
The result follows.

If X is an odd cycle n = e = g and the bound is attained. Also for the complete
graphs Kn , n ≥ 3, we have n vertices, e = n2 edges and g = 3 and the upper

bound is given by n3 n2 − n + 1 = n3 . Since each triple of vertices gives an odd

convex cycle, and there are no others in Kn , the upper bound is again attained.
Azarija and Klavžar [1] now show that this upper bound for odd convex cycles is
attained precisely for Moore graphs.

n
Lemma 6.6. ρo (X) = g
(e − n + 1) if and only if X is a Moore graph.

Proof. Suppose X is a graph such that the equality holds. Then from the proof of
Lemma 6.4 we require that the breadth-first search tree T is such that
|E(T )| = n − 1 and from the proof of Lemma 6.5 we require that each odd convex
cycle C in X is such that |C| = g = 2D + 1 for some integer D ≥ 1. Hence it
suffices to show that X has diameter D since it has girth 2D + 1. From the first
requirement we deduce that every edge f = xy not in E(T ) constitutes an odd
antipodal pair with a distinguished vertex u in X and hence
dX (x, u) = dX (u, y) = D. But for any graph X with a vertex v of degree 1 we have
ρ(X) = ρ(X − v) and hence we may assume each vertex of X has degree at least 2.
It follows that if x is a leaf of the tree T then it is incident with an edge f not in
E(T ) but in E(X) and hence dX (x, u) = D and thus X has diameter D as
required.

B0524984 Sanjeev Gupta

6.2 Even Convex Cycles 34

Conversely we show that each graph in Table 1.1 satisfies the equality by using the
results of Section 4.1 to count the number A of odd cycles of length 2D + 1, each
such cycle being convex.

Table 6.1: Bound for odd convex cycles in Moore Graphs

deg. Diam. Name n e g U. Bound A
d(d+1) d+1

d+1


d 1 Kd+1 Complete d+1 2
3 3 3
2 D (2D + 1)-gon 2D+1 2D+1 2D+1 1 1
3 2 Petersen 10 15 5 12 12
7 2 Hoffman-Singleton 50 175 5 1260 1260
57 2 Missing Moore 3250 92625 5 58094400 58094400

In each case the upper bound is attained and the result is proved.

Azarija and Klavžar [1] note that from Lemma 6.6 we may immediately deduce

Theorem 6.7. A simple graph X with n vertices, e edges and girth g = 2D + 1 is a

n
Moore graph if and only if the number of (2D + 1)-cycles in X is 2D+1
(e − n + 1) .

6.2 Even Convex Cycles

They continue by considering even convex cycles in X. As for the odd case we
begin with a combinatorial argument.

Lemma 6.8. For any u ∈ V (X) there are at most e − n + 1 vertices v such that
(u, v) is an even antipodal pair.

Proof. Take any u ∈ V (X). If (u, v) is an even antipodal pair of the even convex
cycle C, let T be the breadth-first search tree with u as the distinguished vertex.
By Lemma 6.3 every even convex cycle containing u is uniquely determined by the
even antipodal pair (u, v) and every edge of C is in E(T ) except for one of the two
edges of C to which v is incident. Since T has at least n − 1 edges and there are

B0524984 Sanjeev Gupta

6.2 Even Convex Cycles 35

e edges in X there are most e − n + 1 even convex cycles containing u and the
result follows.

Let ρe (X) denote the number of even convex cycles in X.

n
Lemma 6.9. ρe (X) ≤ g
(e − n + 1) .

Proof. There are n vertices in X and by Lemma 6.8 there are at most e − n + 1
vertices with which each vertex can form an even antipodal pair. Since we are
n(e−n+1)
concerned with unordered pairs we have at most 2
such pairs. Each even
antipodal pair determines an even convex cycle C in X, each such cycle being
|C|
determined by 2
even antipodal pairs with |C| ≥ g. The result follows.

Thus we arrive at the result for even convex cycles.

n
Lemma 6.10. ρe (X) = g
(e − n + 1) if and only if X is an even cycle.

Proof. If X is an even cycle then equality clearly holds. Conversely, aiming for a
contradiction, suppose C is an even convex cycle in X with u ∈ V (X) not in V (C)
0
but adjacent to v ∈ V (C). Let v be the antipodal vertex to v on C. For equality
to hold by the proof of Lemma 6.8 we require |E(T )| = n − 1 and by the proof of
Lemma 6.9 we require |C| = 2k for some k ≥ 2 for each even convex cycle C in X.
0
(u, v ) cannot be an even antipodal pair as if it were there would be at least three
0
edges not on a breadth-first search tree with v as the distinguished vertex. Hence
v 0 would be contained in less than e − n + 1 convex cycles and
n 0
ρe (X) ≤ g
(e − n + 1). In addition at least one edge to which v is incident on C is
not on a breadth-first search tree with u as the distinguished vertex and so u is
contained in less than e − n + 1 even antipodal pairs and hence
n
ρe (X) < g
(e − n + 1), the contradiction we seek.

B0524984 Sanjeev Gupta

6.3 The Combined Inequality 36

6.3 The Combined Inequality

Azarija and Klavžar [1] are now in a position to combine the bounds for odd and
even convex cycles giving an inequality for ρ(X) the number of convex cycles in a
graph X. The key insight is that graphs with the maximum number of convex
cycles either contain only even or only odd convex cycles.

n
Lemma 6.11. ρ(X) ≤ g
(e − n + 1). Moreover, if X contains an even convex
cycle then the bound is attained if and only if X = Cn .

Proof. Let C be an even convex cycle in X with (u, v) an even antipodal pair and
T the breath-first search tree with distinguished vertex u. Then if e and f are the
two edges in C to which v is incident, at least one is not on T and cannot form an
odd antipodal pair with u. Thus for every even convex cycle in X there is at least
n
one less possible odd convex cycle and hence ρ(X) ≤ g
(e − n + 1).
If X = Cn an even convex cycle then the bound is attained. Suppose then that X
contains an even convex cycle C and X 6= Cn with u ∈ V (X) not on C but
0
adjacent to v ∈ V (C) and v the antipodal vertex on C. Let Puv0 denote the
0
shortest uv -path in X. We distinguish two possible cases.
Case (i). Puv0 ∩ C 6= ∅.
0
(u, v ) is not an even antipodal pair as condition (iv) of Lemma 6.3 is violated.
0
Also at least one edge to which v is incident on C is not in the breadth-first search
tree with u as the distinguished vertex and hence does not form an odd antipodal
n
pair with u. Thus ρ(X) < g
(e − n + 1).
Case (ii). Puv0 ∩ C = ∅.
0 0
v has degree at least 3 and by convexity of C, |Puv0 | = dX (v, v ). Thus in the
breadth-first search tree with u as the distinguished vertex both edges e and f on
0
C with which v is incident are absent. In addition neither of these edges form an
0
odd antipodal pair with u and since (u, v ) can be an even antipodal pair of
precisely one even convex cycle only, u is contained in strictly less than e − n + 1
antipodal pairs, and again the upper bound for ρ(X) is not attained.

B0524984 Sanjeev Gupta

6.3 The Combined Inequality 37

Combining Lemma 6.11 and the results for odd and even convex cycles
Theorem 6.2 follows allowing us to characterise Moore graphs as those graphs
n
where the number of odd cycles attains its upper bound of g
(e − n + 1).

B0524984 Sanjeev Gupta

Chapter 7

Conclusion

In this dissertation we have sought to classify Moore graphs of type (d, D), simple
graphs with degree d and diameter D. In their paper of 1960 Hoffman and
Singleton [9] defined such graphs to be those simple graphs X of maximum degree
d and diameter D such that the upper bound 1 + d D i−1
P
i=1 (d − 1) on the number
of vertices n is attained. It was shown that when equality is attained X is regular
with degree d and girth g = 2D + 1. By considering graphs of minimum degree d
and odd girth g = 2D + 1 it was shown that the lower bound on the number of
vertices n is 1 + d D i−1
P
i=1 (d − 1) and when this bound is attained we again get a
Moore graph of type (d, D) with girth g and diameter D satisfying g = 2D + 1
leading us to conclude that Moore graphs of type (d, D) can be defined as those
graphs with diameter D and girth g = 2D + 1, such graphs necessarily being
regular and distance-regular. It is for this reason that the Moore graphs are of such
interest and as Damerell [5] has pointed out it is a pity there are so few of them.
We also considered a different classification of Moore graphs due to Azarija and
Klavžar [1]. They showed that a simple graph X with n vertices, e edges and girth
g = 2D + 1 is a Moore graph if and only if the number of (2D + 1)-cycles in X is
n
2D+1
(e − n + 1) .
Using the results of Hoffman and Singleton [9] on Moore graphs with diameter 2
and 3 we have a complete classification of such graphs. Indeed we have shown that
the only Moore graphs of diameter 1 are the complete graphs Kn with degree
n − 1, and the only Moore graphs with diameter 2 are the cycle C5 with degree 2,
the Petersen graph with degree 3, the Hoffman-Singleton graph with degree 7, and
possibly the so-called Missing Moore graph with degree 57, whilst the only Moore

B0524984 38 Sanjeev Gupta

7 Conclusion 39

graph with diameter 3 is the 7-cycle C7 .

Damerell [5], and independently Bannai and Ito [2], showed that no Moore graphs
exist for diameter D ≥ 3 other than the (2D + 1)-sided polygons.
Thus we are left with the problem of determining whether a Moore graph of
type (57, 2) exists or not, a long-standing open problem in graph theory. We have
seen that if such a graph exists then it has certain known properties. Indeed we
have shown how many cycles of length up to 9 pass through any given vertex of
such a graph. We have also shown that any such graph cannot be vertex-transitive
and we investigated the size of an independent set within it. This provided us with
a possible way to define such a graph using the projective space P G(3, 7) but we
have seen that there still remain problems with this approach, specifically in
determining a suitable adjacency relation between the lines of the projective space.
Using the results of Chapter 3 we note that a possible Moore graph of type (57, 2)
with adjacency matrix in canonical form would have 57 + 57 · 56 + 56 · 56 = 6385
56·56·55
edges determined by the canonical construction, leaving 2
= 86240 edges
between tier 2 vertices still undecided, the sheer number of edges illustrating the
difficulty in using combinatorial approaches to determine these remaining
adjacencies.
Higman’s approach in showing that a possible Moore graph X of type (57, 2)
cannot be vertex-transitive was based on a detailed analysis of a single
automorphism of X. Mačaj and Širáň [10] instead analysed entire subgroups of
automorphisms of X and how the automorphisms within a subgroup influenced
each other. It is likely that future research follows their approach to investigate
further restrictions on the order of the automorphism group of X thereby leading
to possible configurations for Moore graphs of type (57, 2).

B0524984 Sanjeev Gupta

Bibliography

[1] J. Azarija and S. Klavžar (2012), Moore graphs and cycles are extremal
graphs for convex cycles, arXiv:1210.6342.

[2] E. Bannai and T. Ito (1973), On finite Moore graphs, J. Fac. Sci. Tokyo Univ.
20, pp. 191-208.

[3] N. I. Biggs (1993), Algebraic Graph Theory, Cambridge University Press,

Second Edition, Great Britain.

[4] P. J. Cameron (1994), Combinatorics: Topics, Techniques, Algorithms,

Cambridge University Press, Cambridge.

[5] R. M. Damerell (1973), On Moore graphs. Mathematical Proceedings of the

Cambridge Philosophical Society, 74, pp. 227-236.
doi:10.1017/S0305004100048015.

[6] H. D. Friedman (1971), On the impossibility of certain Moore graphs, J.

Combin. Theory, 10, pp. 245-252.

[7] C. Godsil. So few Moore graphs. http://quoll.uwaterloo.ca/pstuff/moore.pdf.

Accessed on 17 Oct. 2013.

[8] C. Godsil and G. Royle (2001), Algebraic Graph Theory, Volume 207 of
Graduate Texts in Mathematics, Springer-Verlag, New York.

[9] A. J. Hoffman, R. R. Singleton (1960), On Moore Graphs with Diameters 2

and 3, IBM Journal of Research and Development 4, pp. 497-504.

[10] M. Mačaj and J. Širáň (2010), Search for properties of the missing Moore
graph, Linear Algebra and its Applications 432, pp. 2381-2398.

B0524984 40 Sanjeev Gupta

BIBLIOGRAPHY 41

[11] J. Plesník (1974), One method for proving the impossibility of certain Moore
graphs, Discrete Mathematics 8, pp. 363-376.

[12] R. R. Singleton (1968), There is no irregular Moore graph, Amer. Math.

Monthly 75, pp. 42-43.

[13] S. Warner (1990), Modern Algebra, Dover ed.

B0524984 Sanjeev Gupta