 

(to:
..L
"w

.7 . ya.»

4..

.kwmwm 5er

..
X J u
ﬁamﬁWJEmE h ﬂWm

..
u .
kw.» .

up. in}.

.3

ﬁe

£53.63 v
r ..

«A

 

.. Li‘zln.V|:.
v: ll.'l|‘ I;

sawiﬁgﬁw ; ‘. ‘ _ ‘ ,. g? .

 

 

 

'W

(I i
rt, \
(7 DD
5 707 (to ’7 Ct

This is to certify that the
dissertation entitled

IMPRIMITIVE DISTANCE-TRANSITIVE GRAPHS

presented by

Monther Rashed Furaidan

has been accepted towards fulfillment
of the requirements for the

Ph.D. degree in Mathematics

 

 

Q\w~9\\~—~2 .M

 

)‘ Major Professor’s Signature

‘ﬁ mAWM\ 100+

 

Date

MSU is an Afﬁrmative Action/Equal Opportunity Institution

_.v...-.—.-._... __r_.

_ —....—..-.-._..»....

vv

 

r.-f-~*—*vm'w“ﬁ'WWw—" _._.~ W‘r’ _'__ﬁ._-_-—'-——-—- --—' —"-"O — f:-

 

 

 

 

.UBRARY
Michigan State
University

 

 

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/ClRC/DateDue.p65-p. 15

IMPRIMITIVE DISTANCE—TRANSITIVE GRAPHS

By

Monther Rashed Furaidan

A DISSERTATION

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

2004

ABSTRACT

IMPRIMITIVE DISTANCE-TRANSITIVE GRAPHS
By
Monther Rashed F uraidan

We present the conjectured list of primitive distance transitive graphs of diameter at least
3. For each graph G on this list we attempt to classify all imprimitive distance-transitive
graphs that are antipodal covers of G or have C as halved graph. This classiﬁcation is
successful in all cases except when G is a generalized 2d—gon, where the distancetransitive

antipodal covers of diameter 2d remain unclassiﬁed.

Copyright:© Monther Alfuraidan 2004

To my parents and my wife

iv

ACKNOWLEDGEMENTS

Praise be to ALLAH, Lord of the Word, the Almighty, with Whose gracious help it was
possible to accomplish this task.

First and foremost, I have to thank my thesis adviser, Professor Jonathan 1. Hall, whom I
consider to be my father in a foreign land. He has given me valuable insight, both personally
and academically. I am indebted to him for his continual, unwavering support of my work
and his incredible patience with me, especially during stressful times like my journey into
fatherhood.

I am also grateful to my thesis committee in the Mathematics Department at Michi-
gan State University: Professors Ulrich Meierfrankenfeld, Bruce Sagan, Jeanne Wald, and
Michael Frazier. I am particularly thankful for the hours and hours Michael and Jeanne
spent practicing and preparing me for my qualifying exams.

I am forever indebted to Professor Mohammed Albar, former Chairman of the Mathe-
matics Department at King Fahd University of Petroleum and Minerals in Saudi Arabia. He
is the ﬁrst person who saw my potential as a mathematician and encouraged me to change
my major from engineering to mathematics. He has always supported my academic and
teaching efforts. I am also indebted to KFUPM for sponsoring me and providing me with
the ﬁnancial resources necessary to complete my studies in the United States.

I would be remiss if I did not mention the support of my mother, Munairh Ali Alsaqar.
Her love, care and prayers have given me the strength to endure through times of trouble. I
am especially grateful for her patience; it was very difﬁcult for her to be separated from her
youngest child for over 6 years while I studied abroad. I only hope that she is proud to be
called the mother of Dr. Monther Alfuraidan.

He died when I was 2 years old, but I am so grateful for my father’s legacy to me. I have
no memory of him, but I have known him all my life. Everyone who has ever spoken of him

has told me what a caring, generous, intelligent, sensitive man he was. I only hope that I

 

 

 

 

.u- _. J
\ f

—| u-‘\~\
9‘" .
u_ .4

 

- .
5., .,
I
"‘ 0A.
- »..,
‘ D
I.-
.. ,4
c- i-

 

 

..
0- _. '

. -‘ — '
‘5‘: .f‘

 

can live up to his memory, and I pray to see him someday in heaven.

The rest of my family has also been very supportive with prayers and best wishes for
my success. I am grateful every day for my brothers, Mohammed and Salah, and my sister
Fatima. They have waited a long time for my return, and I am happy to see them soon.

To my brothers in the United States, Muhannad Yousef and Awad Alqahtani, thank you
for being my family away from home. You reminded me of my roots and kept our culture
alive.

To all of my friends, both in the United States and in Saudi Arabia (you know who you
are), I love you all for your continual faith in me and cheerful phone calls.

Finally, to my beautiful wife, Awatif Mohammed Alnowibit, I owe everything I am and
everything I have to her. She has bravely sacriﬁced her life, her education and her family to
be with me as I completed my studies in a foreign land, completely unknown to her. And in
that land, she gave me my ﬁrst-born son, Rashed. Together, they are all things wonderful

and I love them more than life.

vi

 

 

 

 

:i. J

.7 J

21'.-

fi ..

.3

Contents

1 Introduction 1
1.1 Basic Deﬁnitions ................................ 1
1.1.1 Graph theory .............................. 1

1.1.2 Design theory .............................. 4
1.2 Graphs and Groups .............................. 5
1.3 Transitivity in Graphs ............................ 7

2 Distance-Transitive Graphs 11
2.1 Deﬁnitions and Examples .......................... 11
2.2 Parameters and Feasibility of Intersection Arrays ........... 13
2.3 Regular Partitions ............................... 19
2.4 Imprimitive Distance—Regular Graphs ................... 20
2.5 Bounding the Diameter ............................ 24

3 Primitive Distance-Transitive Graphs 26
3.1 The Starting Point in the Classification ................. 27
3.2 Primitive DTGs of Afﬁne Type ....................... 28

3.2.1 The one dimensional afﬁne case .................. 29
3.2.2 The afﬁne alternating ......................... 30

3.2.3 The afﬁne groups of exceptional Lie type in same characteristic 30
3.2.4 The afﬁne groups of classical Lie type in same characteristic 31

3.2.5 The afﬁne groups of Lie type of cross characteristic ...... 31

3.2.6 The afﬁne sporadic groups case ................... 32

3.3 Primitive DTGs of Simple Socle Type .................. 32

3.3.1 The alternating simple socle ..................... 33

3.3.2 The simple socle of Lie type ..................... 33

3.3.3 The sporadic simple socle ...................... 36

4 Statement of Main Results 37
4.1 Known Primitive Distance-Transitive Graphs of

Diameter at Least Three ........................... 37

4.2 Covers and Doubles .............................. 39

vii

l,

 

 

5 Antipodal Covers 44

5.1 Quotient Graphs ................................ 45
5.2 Inﬁnite Families ................................ 50
5.2.1 Johnson graphs ............................. 51
5.2.2 Odd graphs ............................... 54
5.2.3 Hamming graphs ............................ 55
5.2.4 Grassmann graphs ........................... 56
5.2.5 Dual polar graphs ........................... 57
5.2.6 Sesquilinear forms graphs ...................... 59
5.2.7 E7 graphs ................................ 60
5.2.8 The afﬁne E6 graph .......................... 61

5.3 Isolated Examples ............................... 61
5.3.1 Witt graphs ............................... 62
5.3.2 Golay graphs .............................. 63
5.3.3 Afﬁne sporadic graphs ........................ 66
5.3.4 Simple socle graphs of Lie type ................... 71
5.3.5 Sporadic simple socle graphs .................... 76

5.4 Generalized 2d-gons .............................. 78
6 Bipartite Doubles 79
6.1 Halved Graphs ................................. 79
6.2 Infinite Families ................................ 82
6.2.1 Polygon ................................. 82

6.2.2 Johnson graphs ............................. 83
6.2.3 Quotient Johnson graphs 7(2k, k) .................. 83
6.2.4 Odd graphs ............................... 84
6.2.5 Hamming graphs ............................ 84
6.2.6 Quotient Hamming graphs EM, 2) ................. 84
6.2.7 Grassmann graphs ........................... 84
6.2.8 Dual polar graphs ........................... 85
6.2.9 Bilinear forms graphs ......................... 86
6.2.10 Alternating forms graphs ....................... 86
6.2.11 Hermitian forms graphs ....................... 86

6.3 Isolated Examples ............................... 86
6.3.1 Afﬁne sporadic graphs ........................ 87
6.3.2 Simple socle graphs of Lie type ................... 91
6.3.3 Sporadic simple socle graphs .................... 95

6.4 Generalized 2d-gons .............................. 98

viii

Lie

3.2

 

 

List of Tables

3.1
3.2
3.3
3.4

4.1
4.2

afﬁne sporadic distance-transitive graphs .................... 32
graphs with distance-transitive groups A such that F *(A) 2 PS L(n, q) . . . 35
the rest(known) DTGs with simple socle Lie type groups ........... 35
simple socle sporadic distance—transitive graphs ................ 36
primitive distance-transitive graphs ....................... 38
aSsociated imprimitive distance-transitive graphs ................ 4O

ix

 

 

. .
is.»

a.
,- 3

 

List of Figures

1.1
1.2
1.3

3.1
3.2
3.3

5.1
5.2

6.1
6.2

a vertex-transitive graph that is not edge-transitive .............. 8
Folkman graph .................................. 9
a graph that is neither vertex- nor edge-transitive ............... 9
primitive main tree ................................ 28
afﬁne tree ..................................... 29
simple socle tree .................................. 33
antipodal main tree ................................ 45
antipodal covers of classical DTGs tree ..................... 51
bipartite doubles main tree ............................ 80
bipartite doubles of large diameter DTGs tree ................. 83

 

 

 

3.x
J.
'5 l
.,<
u .

 

 

.
~

-

a

s

List of Symbols

Group Theory

A,B
X

A 2 B
B S A
B _<_1 A
NA(B)
soc(A)

Zn
M11,M12,M22, M23,1V124
PGL(n, q)

PSL(n, q

PFL(n, q)

AGL(n, q)

APL(n, q)

GF(Q)) F0

WM (1)

P001, (1)

AG(n, q)

N

Graph and Design Theory

G, H
I

B

L

at
V(G)
E(G)
C(u)
MG)

groups

set

wreath product of A of B

B is a subgroup of A

B is a normal subgroup of A
normalizer of B in A, where B S A
socle of A

stabilizer of :1: in A

setwise stabilizer of X in A
symmetric group on X

symmetric group of degree n
alternating group of degree n
additive group of integers modulo n
Mathieu group

projective general linear group
projective special linear group
semilinear projective group

affine group

semilinear afﬁne group

ﬁnite ﬁled with q elements
n-dimensional linear space over GF (q)
projective geometry

afﬁne geometry

equivalence relation

graphs

incidence relation

set of blocks

set of lines

distance graph

vertex set of G

edge set of G
neighborhood of u in G
line graph of G'

.1. r

Aut(G)

k

d, d(G), D

d(u, v)

9,9(G)

00/, E)

5, 50/, E), G/P
0+, 0-, ,0

at: bi: 01
1(0)
DRG
DTG
J(n, 19)
2J(n, k)
Jq(n, k)
2Jq(n, k)
Qn, H(n, 2)
TM

®

H (n, q)
0!:

2O,c
Alt(n, q)
Hq(na (I)
Her(n, q)
S(t, k, 1))

full automorphism group of G

valency of a regular graph

diameter of G

distance between u and v

girth of G

complement of G

quotient graph of G (with respect to P)
halved graphs of G

complete graph with n vertices
complete bipartite graph with n vertices
in each part

complete n-partite graph with t, vertices

,_ 7; in the 2' part

cycle with length n

path with length n

partition of V(G)

covering index (ﬁbre size)
intersection numbers
intersection array of the distance-regular graph G
distance-regular graph
distance-transitive graph
Johnson graph

double Johnson graph
Grassmann graph

Grassmann graph

n-cube

triangular graph

direct products of graphs

is adjacent to

Hamming graph

odd graph

double odd graph

alternating forms graph over F,
bilinear forms graph
Hermitian forms graph over qu
Steiner system

Chapter 1

Introduction

1.1 Basic Deﬁnitions

1.1.1 Graph theory

A graph G = (V, E) is a nonempty set of elements called vertices together with a (possibly
empty) set of elements called edges. Each edge is identiﬁed with a pair of vertices. The
vertices v,- and vjassociated with an edge e are called the end vertices of e. The edge e is then
denoted by e = (22,-, 12,-) or simply e = v.25. If e = 21,24, then the edge e is called a self-loop at
vertex 7),. All edges having the same pair of end vertices are called parallel edges. A graph is
simple if it has no parallel edges or self-loops. In this thesis, we will always be considering
simple, undirected, ﬁnite graphs.

As usual, IX | denotes the number of elements in a set X. For a graph G, if |V| = n and
(E! = m, then G is called an (n, m) graph; the number n is also referred to as the order of
G and m as the size of G. A graph with no edges is called an empty graph. A graph with
no vertices (and hence no edges) is called a null graph.

The edge e = vivj is said to join the vertices v,- and 22,-. If e = vivj is an edge of a

graph G, then 21, and v, are adjacent vertices, while 1),- and e are incident, as are '03- and e.

1

.-

’u~'.

A w

 

 

 

...4II- . ;

 

Furthermore, if 61 and 62 are distinct edges of G incident with a common vertex, then 61
and 82 are adjacent edges. The number of edges incident on a vertex v,- is called the degree
of the vertex, and it is denoted by deg(v,-). A vertex of degree 1 is called a pendant vertex.
A vertex of degree 0 is called an isolated vertex.

Given a nonempty graph G, the line graph L(G) of G is the graph whose vertices can
be put in one to one correspondence with the edges of G in such a way that two vertices of
L(G) are adjacent if and only if the corresponding edges of G are adjacent.

A graph G is said to be regular if deg(u) 2 (169(2)) for all u,v E V(G). It is k-
regular if deg(v) = k for all '0 E V(G); in this case, the number k is also referred to as
the valency(degree) of G. A 3-regular graph is frequently described as a cubic graph, or
sometimes as a trivalent graph.

A regular graph with ’0 points and valency k is called edge-regular with parameters
(v, k, A) if any two adjacent vertices have exactly A common neighbors.

A graph G’ = (V’, E’) is a subgraph of G = (V, E) if V’ g V and E’ Q E such that
an edge vivj is in E’ only if v,- and v, are in V’. If v,- is a vertex of a graph G = (V, E),
then the graph G - v,- = (V’, E’) is the graph obtained after removing from G the vertex v,-
and all the edges incident to 11,-. If e,- is an edge of a graph G = (V, E), then G —— e,- is the
subgraph of G obtained after removing from G the edge e,-. The graph G = (V, E’) is called
the complement of graph G = (V, E) if the edge 12in is in E’ if and only if it is not in E.
Hence, if G is an (n, m) graph, then G is an (mm) graph, where m —l- 77:: = (’2’).

A walk in a graph G = (V, E) is a ﬁnite alternating sequence of vertices and edges
on, 61,111,62, ...,vk_1, ek_1,i1k beginning and ending with vertices such that v,_1 and v, are the
end vertices of the edge 6,, 1 S 2' S k. A walk is open or closed depending on whether its
end vertices are distinct or are not distinct. A trail is a walk in which no edge is repeated,
while a path is a walk in which no vertex is repeated. A closed trail is a cycle if all its

vertices except the end vertices are distinct. The number of edges in a path (cycle) is called

3... .... l
l . v
a . ldk w~ lit . .
.. .3. : .. _
x . , 1 4.1.9.

 

 

 

the length of the path (cycle). A graph G is connected if there exists a path between every
pair of vertices in G. Otherwise, we say G is disconnected. A maximal connected subgraph
of a disconnected graph G is called a component of G.

The distance d(u, '0) between two vertices u and v in G is the length of a shortest path
joining them if any; otherwise d(u, v) = 00. A shortest u — v path is often called a geodesic.
The diameter d(G) (or simply d) of a connected graph G is the length of any longest
geodesic. The girth g(G) ( or simply g) of G is the length of the shortest cycle in G if any;
otherwise g(G) = 00. A k—regular graph of smallest positive integer order with girth g is
called an (k,g)-cage. The (3, g)-cages are commonly referred to simply as g-cages.

A (k, 2d+1)-cage is better known as a Moore graph and a (k, 2d)-cage as a generalized
polygon where d is the diameter of the cage.

The complete graph Kn has every pair of its n vertices adjacent. Thus Kn has (’2‘)
edges and is a (n — 1)-regular.

An r-matching in a graph G is a set of 'r edges, no two of which have a vertex in
common.

A graph G is n-partite, n 2 1, if it is possible to partition V(G) into n subsets
V1, V2, ...,Vn such that every edge of G joins a vertex of V,- to a vertex of V], 2' ;£ j. For
n = 2, such graphs are called bipartite graphs. A complete n-partite graph G is an
n-partite with partite sets V1, V2, ..., Vn such that no 6 E(G) for all u E V, and v E V,- with
z' 79 j. If |V,-| = t,, then this graph is denoted by K(t1,t2, ...,tn). For n = 2, the complete
bipartite graph with partite sets V1 and V2, where WI] 2 m and |V2| :- n, is then denoted
by K (m, 12.).

Two graphs G1 and G2 are said to be isomorphic if there exists a one to one mapping
6, called an isomorphism, from V(Gl) onto V(Gg) such that cf) preserves adjacency, that is

rm 6 E(G’l) if and only if qiuqbv E E(Gg).

4113.51.43 1.x:
:1

. .

 

 

..
" \
.m-
w
a

nu” .

V' ‘.
( ‘-
... ~

L."
sui~
l
<’
.1
"i
P‘;
~‘.
I.
. »
~
I
4Q
IKV
.
\L 'l
. ‘._
I

 

 

.h
r v
s
t
\‘ I
'l
’I
N '-
‘5
, o
x. t
g
‘1.
\. ‘r _
T l
M.
“‘ .vr.
~Q
I

..
.\- r
ne‘k
‘5'
o ‘i .
\
\ “‘,
\
c‘\_
x
‘
. i
\ .
‘\
\.
. 1 '1
M
«a
\
..
.\ ,
~. ~

1 . 1.2 Design theory

A design is an ordered pair (X, %) with point set X and set of blocks ‘3 such that ‘B is a
collection of subsets of X. More generally, it is an ordered triple (X, ‘B, I), where X and %
are sets and I is a subset of X x %, called the incidence relation.

The point graph of the design (X, ’B, I ) is the graph whose vertex set is X and in which
two points are adjacent whenever there is a block containing both. The dual of the design
(X,‘.B,I) is the design (SB,X,I’), where I, = {(B,:c)|(:c,B) E X x E}. A design is called a
self-dual if it is isomorphic to its dual. The incidence graph of a design (X, ‘B, I ) is the
bipartite graph with vertex set X U 53 and edge set {{x, %}I(:c, 58) E I}.

A t-(v,k,A)-design is a pair 33 = (X, 58), where X is a set of points of cardinality v, and
B a collection of k-element subsets of X called blocks with the property that any t points
are contained in precisely A blocks.

A Steiner system S(t,k,v) is a t-(v, k, 1) design. A square (or symmetric) 2-design
is a 2-(v, k, A) design with just as many points as blocks.

A partial linear space is a design (X, 2) in which the blocks are called lines such that
the line have size at least 2 and two distinct points are joined by at most one line.

If u is a vertex of a graph G, we deﬁne ul 2 G51(u) :2 {u} U {U E V(G)| d(u,v) = 1},
and if X is a set of vertices of G, we deﬁne Xi : {ﬂuiiu E X}. If G is edge-regular, then
G is the point graph of the partial linear space whose lines are the subsets {21,21}ii for all
adjacent vertices u, v E G. These lines are known as singular lines.

A graph with the property that each edge lies in a unique maximal clique is a collinearity
graph of the partial liner space, formed by the vertices of the graph as points and the
maximal cliques of it as lines. In other words, the collinearity graph is the point graph of a
partial linear space.

A ﬁnite projective plane of order n, denoted PG (2, 77.), consists of a set X of n2+n+1

elements called points, and a set ’3 of (n + 1)-clemcnt subsets of X called lines, having the

4

 

 

 

VD
..

‘i

‘.

u

'0 .
.,.
u.‘

 

 

 

 

 

 

 

.
‘ 5
‘ \
. o
*4.
‘o
.
‘1!»
.V ..~.
\_
'r
.
x 5‘».
'9
l
.1»

property that any two points lie on a unique line. In other words, PG(2,n) is a square
2-(n2 + n + 1,n + 1,1) design. A ﬁnite afﬁne plane of order n consists of a set X of
n2 points, and a set % of n-element subsets of X called lines, such that two points lie on a
unique line, i.e., a 2-(n2, n, 1) design. A projective or afﬁne plane is Desarguesian if it is
coordinatized by a division ring.

In a similar way, one can deﬁne the n-dimensional projective geometry over GF (q),
denoted PG(n, q), by means of an (71+ l)-dimensional vector space V = V(n+1, GF(q)).The
points are the 1—dimensional subspaces of V; the lines are the 2-dimensional subspaces;
planes are 3—dimensional subspaces and so on. The ﬁnite n-dimensional afﬁne geometry
AG (n, q) over GF (q) is the projective geometry PG (n, q) minus its hyperplane H (a subspace

of codimension 1) together with all the subspaces it. contains.

1.2 Graphs and Groups

It is assumed that the reader is already familiar with basic group theory such as groups,
cosets, direct product, normal subgroups, homomorphisms, isomorphism and factor groups.
In this thesis, we are particularly concerned with the concepts of group actions, orbits,
transitive groups, primitive and imprimitive groups and wreath products. We will include
these only to demonstrate our terminology and notation which varies considerably between
texts.

Let X be a set. The symmetric group on X, written Sym(X), is the set of all permu-
tations of X. It forms a group, with the operation of composition. If X is a ﬁnite set with
n elements, we write S7, for the symmetric group Sym(X). The subgroup of 5,, consisting
of the even permutations of 17. letters is the alternating group A, on 12. letters .

An automorphism of a graph G is an isomorphism of G with itself, that is, a per-

mutation on V(G) that preserves adjacency. The set of all automorphisms of G, with the

 

 

 

 

 

 

 

 

X P
o .7.
‘ ‘ul
‘ n
-
. ‘ T c
k-
- K
‘
‘..
~.
u
. i
.
...\_I
_ _’|
.
.o
~.
_ v-
.
\7.
‘§
’7‘
'«
\
\.;
<
\
x
‘1
,r.
‘-

 

operation of composition, is the automorphism group of G, denoted by Aut(G), which is
thus a subgroup of the symmetric group Sym(V(G)).

An action of a group A on a set X is a map d) : A X X —> X such that

1. 1.3: = :1: for all :1: E X where 1 is the identity element of A;
2. (a1a2)(:r) = a1(a2:r:) for all a: E X and all a1, a2 E A.

Under these conditions, X is called an A-set. An action is said to be faithful if the identity
is the only element of A that leaves every element of X ﬁxed. The order of an arbitrary
permutation group A is |A| and if X is an A-set, then the degree of A is IX |.

Let X be an A-set. For 2:, y E X, let :2: ~ y if and only if there exists a E A such that
as: = y. Then ~ is an equivalence relation on X. The equivalence classes of ~ are the orbits
of A; and we say that A is transitive if there is just one orbit. A group A acting transitively
on X is said to act regularly if A, = 1 for each x E X. An orbital of A is an orbit of A
on the set X X X. The number of orbitals is the rank of A.

Let A be a group acting transitively on a set X. A block is a nonempty subset Y of X
such that Y“ = Y or Y“ F) Y = (b for all a E A. Every group acting transitively on X has
X and the singletons as blocks; these are called the trivial blocks. Any other block is called
nontrivial. A group that acts transitively on a set X with no nontrivial blocks is primitive;
otherwise, it is imprimitive.

Let A be a permutation group of order m = |A| and degree m1 acting on the set X =
{3:1, 2:2, ..., xml}, and let B be another permutation group of order 712 = [B I and degree m2
acting on the set Y = {y1, y2, ..., ymz}. The wreath product A 2 B is a permutation group
of order nlng“ acting on X X Y whose elements are formed as follows: For each a E A and
any sequence (b1, b2, ..., bml) of 7m permutations in B, there is a unique permutation in A 2 B

written (a : b1, b2, ...,bm,) such that for (122,,yj) E X X Y;

(a1b1,b2, ”'abm1)(xi7yj) = (dithbiyj).

6

 

 

 

 

 

'.

ho;

 

W
\
A..—

 

. I"
1‘

 

 

 

 

In this case, A is frequently described as the top group and B as the bottom group.
For example, let A = Cg, the cyclic group of degree 3, which acts on X = {1,2,3} and
B = 52, the symmetric group of degree 2, acting on Y = (a, b}. The three permutations of
C3 may be written as (1)(2)(3), (123), and (132). For 82, we have the permutations (a)(b)
and (ab). The wreath product 03 2 52 has degree 6 = 3.2 but its order is 3.23 = 24. Note

that 32 2 G3 has order 2.32 = 18 and so is not isomorphic to Cg Z 32.

1.3 Transitivity in Graphs

This thesis considers mainly a class of graphs that have special conditions on their automor-
phism groups. In this section, we will deﬁne these conditions in turn, beginning with the
weakest one.

A graph G is vertex-transitive (edge-transitive) if given any pair of its vertices
(edges), there is an automorphism which transforms one into the other, that is, if Aut(G)
acts transitively on V(G) (E(G)).

These two properties are not interchangeable; there exist graphs that are vertex-transitive
but not edge-transitive, vice—versa, also graphs that are both vertex- and edge-transitive and
graphs that satisfy neither property.

To show that vertex-transitive does not imply edge-transitive, we construct a graph G
as follows: take two copies of C5 with the vertices of one labelled 1 through 5 and those of

the other labelled 1’ through 5’; then join 2' to 2", 1 S 2' S 5.( See the ﬁgure below)

F3

\

“nan-£34521

 

 

 

5,.

A.“~

 

ll

 

4i :3!

Figure 1.1: a vertex-transitive graph that is not edge-transitive

G is vertex-transitive, since any vertex 2' can be mapped to any other vertex 3' by the
automorphism which maps 2' —+ z" and z" —> j. However, G is not edge—transitive since the
edge 11’ is in two quadrilaterals while the edge 1’2’ is in only one.

To show that edge-transitive does not imply vertex-transitive, consider Km,” n aé m. This
graph is edge-transitive, but it is not vertex transitive, because it is not regular. Folkman
(1967) constructed a regular edge-transitive graph which is not vertex—transitive. (see the

ﬁgure below)

 

 

Figure 1.2: Folkman graph

The complete graph K3 is an example of a graph that are both vertex- and edge-transitive.

The ﬁgure below gives a graph that is neither vertex— nor edge-transitive.

Figure 1.3: a graph that is neither vertex— nor edge-transitive

We now turn to the deﬁnition of graphs which have a higher degree of transitivity than
either vertex- or edge- transitive graphs. An n-arc in a graph G is a walk of length n with
a speciﬁed initial vertex in which no edge succeeds itself. A graph G is n-transitive if
Aut(G) acts transitively on the set of all n—arcs of G. A l-transitive graph is often known
as a symmetric graph.

We will now deﬁne a class with a symmetry condition that is stronger than any of the

above, namely distance-transitive graphs. A detail information together with the classiﬁca-
tion problem of such graphs will be considered in the rest of this thesis.

A graph G is distance-transitive (DTG) if, for all vertices u, v, :r,y of G such that
d(u, v) = d(x, 3;), there is an automorphism a E Aut(G) satisfying 0(a) = :r and 0(2)) 2 y.

We conclude this introductory chapter with the following hierarchy of conditions:

Distance-Transitive :> Symmetric 2) Vertex—Transitive

10

 

Wv-v—‘a

 

 

 

 

u
' u
‘v
41
a“
_' ,_
’K. _
t‘-
x
V
‘_ '1
t.
.‘ I
\

 

 

Chapter 2

Distance-Transitive Graphs

In this chapter we discuss the basic properties and examples of distance-transitive graphs
and the related distance-regular graphs. The fundamental reference is the book of Brouwer,

Cohen, and Neumaier [17].

2.1 Deﬁnitions and Examples

For any connected graph G with diameter d, we deﬁne G, :2 {(u,v)|d(u,v) = 2'}, the set
of all pairs of vertices at distance i, where O S 2' S d. The sets G,- (0 S 2' S d) are better
known as the distance partition graphs of G. Then, for A g Aut(G), we say that G is
an A-distance-transitive graph if A is transitive on each of the distance partition graphs
G0, ..., Gd; G is distance-transitive if it is Aut(G)-distance-transitive.

Notice that, our deﬁnition here for a distance-transitive graph G is equivalent for that
given last chapter. Also, the distance partition graphs G,- are actually the orbitals of G in
V(G).

Examples of distance-transitive graphs are the complete graphs Kn, the complete bi-

partite graphs Km", and the cycles G". More interesting examples are provided by inﬁnite

11

 

 

 

 

 

 

 

 

families of distance-transitive graphs. We introduce ﬁve of them below.

Johnson graphs J (n, k) (where 1 S k < n) form our ﬁrst inﬁnite family of ﬁnite
distance-transitive graphs. The vertices of J (n, k) are the k-subsets of an n-set, with two
k-subsets adjacent if and only if they intersect in exactly k — 1 elements. The valency of

J(n, k) is k(n — k), the diameter is min(k, n — k), and

SnXZQ, ifn=2k_>_4;
Aut(J(n, k)) g (see [17, section 9.1))

Sn, otherwise.

The second family, the odd graphs 0,, (with k 2 2) have the (k— 1)-subsets of a (2k— 1)—
set as vertices, with two (k — 1)-subsets joined by an edge if and only if they disjoint. The
valency of 0,, is k, the diameter is k — 1, and its automorphism is Sgk_1. 02 is the complete
graph K 3 and 03 is better known as Petersen graph. (see [17, section 91])

The Hamming graphs H (n, q) (where n,q > 1) form our third family. They have
vertex set Z; and two vertices are adjacent if and only if they differ in just one position.
The valency of H(n, q) is n(q — 1), the diameter is n, and Aut(H(n, q)) = Sn 2 Sq. H(n,q) is
primitive distance—transitive if and only if q 2 3. If q = 2, it is bipartite and better known
as the n-cube. (see [17, section 9.2))

The fourth inﬁnite family of ﬁnite distance—transitive, the Grassmann graphs Jq(n, k)
(where 1 S k < n) have the k-dimensional subspaces of an n-dimensional vector space over a

ﬁeld E, as vertices, with two of the k-subspaces joined by an edge if and only if they intersect

(qk-1)(q""‘+‘-—q)

(q_1)2 and its diameter

in a subspace of dimension k — 1. The valency of Jq(n, k) is
is min(k, n — k).

The bilinear forms graphs Hq(n, d) (where n 2 d) have as vertices the n X d matrices
over R, with two matrices joined by an edge if and only if their difference has rank 1. (see

[17, section 95])

Some others related families will be introduced next chapter.

12

 

2.2 Parameters and Feasibility of Intersection Arrays

Distance-transitive graphs have rich combinatorial structure. This structure alone enables
one to develop an interesting theory and to carry out a classiﬁcation. For this reason and
many others, it is natural to study such properties in the class of DTG’s.

For a vertex v of a connected graph G with diameter d, and 2' S (1, deﬁne G,(v) 2:
{u E V(G)|d(u,v) = 2'}, the set of vertices at distance 2' from v. For each 2) in V(G), V(G)
is partitioned into the disjoint subsets G0(v), ..., Gd(v), the distance partition of V with
respect to v.

For any connected graph G, any vertices u, v of G, and any non-negative integers h and
2', deﬁne sh,(u, v) to be the number of vertices of G whose distance from u is h and whose

distance from v is i. That is,
...,(u v) = MM 0 one»

If G is distance—transitive graph, then the numbers sh,(u, 1)) do not depend on the par-
ticular vertices u, v one choose, but only on the distance j between them. So, if d(u, v) = j
we write Shij for syn-(u, 1)).

Clearly there are (d+ 1)3 of these numbers, but it turns out that there are many identities
relating them and just 2d of them are sufﬁcient to determine the rest.

For the numbers slij which are not zero we will use the notation
Ci = 31,1—14‘: at = 51,1,“ bi = 51,i+1,i

where 0 S 2' S d and co and bd are undeﬁned.

These numbers (c,-, a,, b,-) have the following simple interpretation in terms of the distance
partition graphs G,- (0 _<_ i S d). Let t) E V(G). For each 2', pick a vertex u E G,(v). Then
a,, b,-, c,- are the numbers of vertices adjacent to u and lying in G,(’v), Gi+1(v) (if z' < d), and

G,_1(v) (if 2' > 0), respectively. By distance transitivity these numbers are independent of

13

 

the choices of the vertices u and 1), provided that d(u, v) = 2'. It is sometimes convenient to

picture these parameters as follows:

or assemble them as an array

* C1 C2
{ (10 0.1 (12
be b1 b2

ad—l ad
Cd—l Cd
(Id—1 ad }
bd_1 *

It is easy to see that ai+bi+ci =kfor 1 S 2' S d—l and cd+ad=kwherekis the valency

of G. Hence the middle row in the array can be omitted. Thus the array can be written as

{k,b1,b2,...,bd..1;1,C2,...,Cd}.

This array is known as the intersection array and is denoted by i(G).

Examples:

 

1. 2'(K4)=={3;1}

14

2- ’ 2'(K3,3) = {3, 2; 113}

 

3. z’(H(3, 2)) = {3, 2, 1; 1, 2,3}

(H(3,2))0 (H(3,2))1 (H(3,2))2 (H(3,2))3

2(03) 2 {3, 2,1,1}

Denote by k, (0 g 2' S d) the number of vertices in G,(v) for any vertex v; in particular
k0 = 1 and k1 = k.

There is an important purely combinatorial analogue to distance transitivity, which sim-
ply asks the numerical regularity properties, namely that the numbers a,, 1),, and c,, are

well-deﬁned, regardless of whether there are any automorphisms that force this to occur. A

15

Hillhhhﬁrhi

 

 

 

 

 

 

connected graph G is called distance-regular graph (DRG) if it is regular of valency k,

diameter d, and if there are natural numbers
b0 2 k,b1,...,bd_1,cl :1,C2,...,Cd
such that, for all 11,21 E V(G) with d(u, v) = i, we have
1. c,- = |G,~_1(v) ﬂG1(u)| (1 S i S d);
2- bi = lGi+1(U) ﬂ Gl(u)] (0 S i S d — 1)‘

A distance-regular graph of diameter 2 is also called strongly regular.

Clearly, any distance-transitive graph is distance-regular, but the converse is certainly not
true. Although many familiar examples of distance-regular graphs are distance-transitive,
Adel’son-Velskii et a1. (1969) construct the following example.

Let G be the graph with vertex set the 26 symbols a,,b,- (where 0 S i g 12), and in
which:

a,~a,- <:> li—jl = 1,3,4
b,- ~bj a) li—jl = 2,5,6
a,~b,- <:>i—j=0,1,3,9.
Then G is distance-regular with intersection array {10,6; 1,4}. But G is not distance-
transitive since there is no automorphism taking a vertex a,- to a vertex b,.
The parameters of a distance-regular graph are subject to many simple but still very

useful constraints. We prove some of the basic restrictions that may be needed later. (see

[17, chapter 5] for more details)

Proposition 2.2.1. Let G be a distance-regular graph with valency k and diameter d. Then
the following hold:

1- ki-lbi-l = kici (1 S i S d);

16

 

. "-d"‘" n—

J

2. If k,- is odd then a,- is even,
3.1Sc23...gcd,

4- k 2 b1 2 Z bit—1;

5. Ifi+j Sd thencj _<_b,-

Proof. (1) For any vertex v E V(G), there are k,_1 vertices in G,_1(v) and each is joined
to b,_1 vertices in G,(v). Also, there are k,- vertices in G,(v) and each is joined to 0,-(v)
vertices in G,-_1(v). Thus the number of edges joining a vertex in G,_1(v) to a vertex in
G,(v) is k,_1b,_1 = k,c,-.

(2) Let U be a ﬁxed vertex in G. The subgraph of G induced by the vertices in G,(v) is
regular with valency a, and has k,- vertices. Hence kia, must be even.

(3) Suppose a is in G,+1(v) (1 S i S d —- 1). Pick a path 11,12, ...,u of length i + 1; then
d(x, u) Z i. Then 21. E G,(a:) and any vertex adjacent to u and at distance i — 1 from :r is at
distance i from 1). Hence G(u) ﬂ G,-_1(a:) is contained in G(u) ﬂ G,(v). But the cardinality
of the ﬁrst is c,-, while of the second is c,+1.

(4) Suppose u is in G,(v) (0 S i g d — 2). Pick a path x,v, ...,u of length i + 1; then
d(as, u) = i + 1. Then a E G,-+1(:r) and any vertex adjacent to u and at distance i + 2 from
:r is at distance i+ 1 from '0. Hence G(u) ﬂ G,+2(:r) is contained in G(u) ﬂ G,+1(v). But the
cardinality of the ﬁrst is bi“, while of the second is b,.

(5) Suppose a E G,(v) and w E Gj('u) with d(u, w) : i+j. Any vertex at distance j — 1
from w and adjacent to v is at distance i + 1 from u. Hence G(v) ﬂ Gj_1(w) is contained in

0(1)) ﬂ Gi+1(U). Thus Cj S Di lf2+j S d. I

The following results are due to Brouwer, Cohen and Neumaier (see Theorem 5.4 1 & Corol—

lary 5.4.2[17]).

17

Ct:

 

 

s
.c

 

Theorem 2.2.2. Let G be a distance-regular graph of diameter d > 2. If 02 > 1, then either

(332%C2 0TC3ZC2+D2 072616123.

Corollary 2.2.3. Let G be a distance-regular graph of diameter d > 2. If c2 2 2, then

(:3 2 c2 + 2 unless the intersection array is (k, k — 1,1;1,k — 1, k}.

Corollary 2.2.4. (Remark { iii) of Theorem 5.41/17” Let G be a distance-regular graph of

diameter d > 2.
1. If 1 < c3 < 262, then G contains a quadrangle.
2.1fc3zcgzw,thenw=l.

The following result is due to Meredith (see (5) [33]).

Theorem 2.2.5. Let G be a distance-regular graph of diameter d 2 3. If a1 = 0 and c2 2 2,

then c,-+1> c, for each 1 S i S d — 1.

Proof. Since G is distance-regular, given any pair of vertices at distance 2, there are c2
paths of length 2 joining those vertices. Since a1 = O and c2 2 2, G has girth 4. Hence each
pair of adjacent edges of G is in precisely (c2 — 1) 4-cycles. Now, let p E Gi+1(u) be adjacent
to q, in G,(u) for 1 S s S c,-+1 and q] to rt in G,_1(u) for I S t S c,-. Then each pair pql,
qlrt is on (c2 - 1) 4-cycles, so there are c,-(c2 —— 1) such cycles. Each of these contains a pqs

edge for some 2 S s S c,+1, so as each pair pql, pqs is on at most (c2 — 1) 4-cycles, we have
(C141 —1)(C2 — 1) 2 61(62 — 1)

i.e. c,+1 > c,. I

The study of distance-regular (transitive) graphs often proceeds by constructing a list
of possible intersection arrays and then trying to ﬁnd the actual graphs with those arrays.
We can view the above restrictions as examples of feasibility conditions that must be

satisﬁed by the intersection array of any distance-regular (transitive) graph. A feasible

18

”’31

array may correspond to zero, one, or several distance-regular graphs G. For example,
{3, 2, 2, 2, 2, 2; 1, 1, 1, 1, 1,3} is feasible but there is no corresponding distance-regular graph,

while {6, 4, 4; 1, 1,3} is realized by exactly two non-isomorphic distance-regular graphs.

2.3 Regular Partitions

Let G =2 (V, E) be a graph. A partition of V is a set whose elements are disjoint nonempty
subsets of V, and whose union is V. A partition P :2 (V1, V2, ..., Vk) of V is called regular
if, for all distinct i and j, the number of neighbors e,~,- which a vertex in V,- has in V,- is
independent of the choice of a vertex in V,~. The partition into singletons is always regular;
the partition {V} is regular only when G is regular. For any group A of automorphisms
of G, the partition of V into A-orbits is regular. This follows since if u and v belong
to the same orbit then there is an automorphism in A which maps a to 1). Since this
automorphism must map each orbit onto itself, it follows that u and 12 have the same number
of neighbors in each orbit. Thus, for a distance-transitive graph G, the distance partition
P(u) = {Go(u), G1(u), ..., Gd(u)} with respect to any vertex a is regular.

The distribution diagram of G with respect to a regular partition P 2 (V1, V2, ..., Vk)
consists of balloons b,-, one for each element V,- E P, and lines l,-,~(= l,,-) joining the two
balloons b, and b,, one for each pair {V,-, V,} for which e,,- at 0. This diagram is provided
with numbers as follows: in the balloon b,- we write [Vi], and at the V,--end of l,,- we write e,,.
The number e,,- is just written next to b,-; when 6,,- = 0, we write —.

Example. The distance distribution diagram of the Petersen graph is shown by the follow-

ing ﬁgure:
03 1.2 10 v = 10.
— 2

19

Given a regular partition P 2 (V1, ..., Vk) of a graph G, the quotient graph G / P of G
with respect to P is the directed graph with the elements V1, ..., V}, of P as its vertices with
e,,- edges going from V,- to V,. Thus G / P has, in general, both loops and multiple edges. If
G / P is actually a (simple) graph then we say that G covers G / P.

If G covers G / P then the subgraphs of G induced by the elements of P are all empty,
since otherwise G / P would have loops. Suppose that V1 and V2 are two elements of P with
at least one edge from a vertex in V1 to a vertex in V2. Since G / P does not have any multiple
edges, each vertex in V1 must consequently be joined to exactly one vertex in V2, and vice
versa. This shows that V1 and V2 have the same cardinality, say r, and that the subgraph of
G induced by the vertices in V1 U V2 is an r-matching. Hence all the elements of P have the
same size r. The common cardinality of the elements is known as the index. In this case G

is called an r-cover of G / P. In this thesis we will always require that r > 1.

2.4 Imprimitive Distance-Regular Graphs

Suppose that A acts imprimitively on the vertex set V of a distance-regular graph G, that is,
there is a nontrivial block B of V. Then each B“ is a block and the distinct blocks B“ form
a partition P = {V1, ..., Vk} of V. Let u,v E V1 and set i :2 d(u,v). As each a E A, ﬁxes a,
it must ﬁx V1 setwise since V1 is a block of imprimitively for A in V. Hence G,(u) g V1. This
observation was strengthened by D. H. Smith [62] to show that there are just two different
kinds of blocks possible, corresponding to bipartite and antipodal graphs. A DRG G of
diameter d is said to be antipodal if there is a partition of the vertex set into classes with
the property that any two vertices in the same class are at distance d, while two vertices in
different classes are at distance less than d. In other words, a DRG G of diameter d 2 2 is

antipodal if Gd is disjoint union of complete graphs. We often refer to the antipodal classes

20

as the ﬁbres of the antipodal graph. Notice that each complete graph is both antipodal and
primitive. Moreover the complete graphs exhaust the antipodal DRG’s of diameter 1. An
antipodal graph of diameter two is complete multipartite.

A distance-regular graph G of diameter d is primitive if the graphs G, (O S i S d) are
all connected; otherwise, it is imprimitive.

The following theorem was proved by Smith [62] for distance—transitive graphs; his proof

is easily extended to arbitrary distance-regular graphs (see [17] pg. 140).

Theorem 2.4.1. Let G be a distance-regular graph with valency k 2 3. If G is imprimitive,

it is either bipartite or antipodal. (Both possibilities can occur in the same graph.)

Thus if V1 is a nontrivial block of imprimitivity containing a, then either G is bipartite
and V1 = {u} U G2(u) U U Gdi(u), where d’ is the largest even integer not exceeding
the diameter d, or G is antipodal of diameter d and V1 2 {a} U Gd(u). In each of these
imprimitive cases it is possible to produce smaller distance-regular graphs.

If G is a bipartite distance-regular graph with diameter (1, then we may represent G by

the following diagram:

 

 

 

.2

G2(u) G101)

 

 

 

 

 

 

 

It turns out that is helpful to consider the distance graph G2. If G is bipartite, connected,
and of diameter d > 1 then G2 has two components and the graphs induced on these

connected components are denoted by G+ and G " (or %G for an arbitrary one of these) and

21

are known as the halved graphs of G. In this case, we say that G is a bipartite distance-
regular(transitive) double (or simply a bipartite double) of %G. The vertices in one
halved graph correspond to a class of cliques in the other. Smith [62] proved that, if G
is distance-transitive graph then its two halved graphs are isomorphic distance-transitive
graphs.

As an example, consider a set X with 21: — 1 elements. The doubled odd graph 20;c
on X is the graph G whose vertices are the (k — l)-subsets and k-subsets of X, where two
vertices u, v are adjacent if and only if u # v and a C v or v C a. It is not hard to show that
2O,c is a bipartite distance—transitive graph. Its halved graphs are copies of J (2k — 1, k).

Now, if G is a distance-regular antipodal graph, then we can represent G by the following

diagram:

 

 

 

 

 

'$\LS

 

 

 

 

’U. U Gd(u)

 

 

 

 

 

 

 

 

 

 

 

01(71) U Gd_1('ll)

Smith [62] proved that, if G is distance-transitive graph then the quotient graph G of G,
deﬁne by taking the ﬁbres of G as its vertices with two such ﬁbres join by an edge in G if
they contain adjacent vertices of G, is a distance-transitive graph. Thus G is actually the

quotient graph G / P with respect to the partition P consists of the blocks {a} U Gd(u) of G.

22

 

Hence G is an r-cover of G, where r is the common cardinality of the ﬁbres (the index of
G). In this case, we say that G is an r-antipodal distance-regular (transitive) cover
(or simply an r-antipodal cover) of G.

The doubled odd graph 20,c is also antipodal. Each ﬁbre consists of a k — l-subset
of X, together with its complementary (k)-subset. The quotient graph G of 2O;c is the Odd
Graph 0],.

In order to gain more insight into the structure of the imprimitive distance—regular graphs

let us consider the following theorem which is due to Biggs & Gardiner (see pg. 141 [17]).

Theorem 2.4.2. Given a distance-regular graph G, we obtain a primitive distance-regular
graph in at most two steps (except in the case of 8n-gons). More precisely, suppose that G

is distance-regular graph of valency k 2 3.

1. If G is antipodal with quotient graph G, then G is not antipodal, except when G has
diameter d S 3, in which case G is complete, or when G is bipartite of diameter d = 4,

in which case G is complete bipartite.
2. If G is bipartite with halved graph éG, then %G is not bipartite.
3. If G is antipodal, and either has odd diameter d or is not bipartite, then G is primitive.
4. If G is bipartite, and either has odd diameter d or is not antipodal, then %G is primitive.

5. If G has even diameter d = 2e, and is both bipartite and antipodal, then the graphs %G

are antipodal, G is bipartite, and the graphs %G E’ %G are primitive.

Q

NIH

G, as appropriate.

7

Moreover, if G is distance-transitive, then so are G, %

Proof. 1. If G has diameter e and is antipodal, then having distance in {0, e, d — e, d}
is an equivalence relation in G.

2. If %G is bipartite, then 0 = a1( G) 2 b1— 1, so bl = 1, k = 2.

1
2

23

3. If G is bipartite of diameter 6, then having distance in {0,2, ...,2[%e],d— 2E6], ..., d— 2, d}
is an equivalence relation in G, so (1 =2 2e is even and G is bipartite.

4. If G is antipodal and bipartite of odd diameter, then it is a 2-antipodal cover, and
%G ”E G2 unless d S 3, in which case both %G and G are complete.

5. If %G is antipodal of diameter 6 2 2, then having distance in {0, 2e} is an equivalence

relation in G, so d = 2e and G is antipodal. I

Thus, starting with an imprimitive distance-regular graph we can always construct a
primitive distance-regular graph after halving at most once and taking at most one quotient.
Sometimes the problem of constructing all imprimitive graphs corresponding to a given

primitive one is very nontrivial.

2.5 Bounding the Diameter

One of the ﬁrst major results in the scope of the classiﬁcation of distance-transitive graphs
was the classiﬁcation of the cubic graphs given by Biggs & Smith [8]. Subsequently, Biggs,
Gardiner, Faradjev, A.A. Ivanov, A.V. Ivanov, Praegcr and Smith gave similar determina-
tions of distance-transitive graphs of valency k = 4, 5, ..., 13 (see [29],]33],[36],[37],[38],]48],[64],

[65]). In each case, the essential steps in the determination are as follows:
1. Bound the order of the vertex stabilizer
2. Bound the diameter
3. Test all the ﬁnitely many possible intersection arrays for feasibility.

The ﬁrst step is closely related to the Sims Conjecture which was proved in the early 19803

[24] as a consequence of the classiﬁcation of the ﬁnite simple groups.

24

Theorem 2.5.1. (Sims Conjecture) There is a function f such that if A is a ﬁnite primitive

group in which A, has an orbit of length It > 1, then IAml S f(k).

The truth of the Sims conjecture makes it feasible to extend the classiﬁcation of distance—
transitive graphs having a given small valency k to the classiﬁcation of distance-transitive

graphs of arbitrary valency k.

Theorem 2.5.2. ( Cameron [21], Weiss [71]) There are, up to isomorphism, only ﬁnitely

many ﬁnite distance-transitive graphs of given valency k greater than or equal 3.

To complete this section we formulate a bound on what the diameter actually is. Unfor-
tunately it is not practical for performing calculations. This result is due to Cameron [24]

and Weiss [71].

Theorem 2.5.3. The diameter d of a distancestransitive graph of valency k > 2 is at most

(k6)!4".

25

Chapter 3

Primitive Distance-Transitive Graphs

 

Attention now turns to the classiﬁcation of distancetransitive graphs. This project is
not yet complete. However, the truth of Sims conjecture gives the green light for such a
process to be completed.

The problem can be divided into two stages: ﬁrst ﬁnding the primitive distance-transitive
graphs, and next, for each individual primitive example found, determining all antipodal
covers and bipartite doubles associated to it. In the current chapter, we collect all available

results on primitive distance-transitive graphs of diameter at least 3. (In the following

26

 

chapter, we present a conjectured list of all such graphs.) Our main work, the problem of
determining those imprimitive DTG’s which correspond to a given primitive one of diameter
at least 3 will be discussed in detail in the rest of the chapters.

In view of the determination of all rank 3 groups, for the classiﬁcation of distance-
transitive graphs, we may assume d 2 3. Also, since the only connected distance-transitive
graphs with valency k = 2 and diameter d are the 2d-gon and 2d+ l-gon, we may also assume

1:23.

3.1 The Starting Point in the Classiﬁcation

The ﬁrst analysis of ﬁnite primitive distance-transitive graphs using O’Nan-Scot theorem
was given by Praegcr, Saxl and Yokoyama [60]. Their result is the ﬁrst step toward the

classiﬁcation of ﬁnite primitive DTG’s.

Theorem 3.1.1. (Praegcr, Saml, Yokoyama) Let A act distance transitively on a prim-

itive distance-transitive graph G. Then one of the following holds.

0 G is a Hamming graph H (n, q) or the complement of a Hamming graph H (2, q) and A
is a wreath product. (In this case, the graph G is well known but the possibilities for

the group A are not completely determined).

0 A has an elementary abelian normal subgroup which is regular on V(G). { This case is

referred to as the afﬁne type).

0 A has a simple socle. That is, there is a simple nonabelian normal subgroup N of A
such that A canonically embeds in Aut(N) ( that is, the centralizer CG(N) of N in A is

trivial). ( This case is referred to as the simple socle or almost simple type).

As a summary, we have the following tree.

27

 

G primitive DTG
A = Aut(G)

 

 

 

 

 

 

 

 

 

 

A of affine type C is H(n, q) or H(2, q) A of simple socle type I

 

 

 

 

 

 

 

 

Figure 3.1: primitive main tree
3.2 Primitive DTGs of Afﬁne Type

In this section, we discuss the classiﬁcation of the primitive afﬁne DTGs.

The main example of graphs admitting distance-transitive action of afﬁne type is the
Hamming graph H (n, q). The bilinear forms graph Hq(n, m) gives another classical example
of an affine DTG. Further examples can be constructed as follows.

The Hermitian forms graphs H er(n, q) (where n, q > 1) have as vertices the n X n
Hermitian matrices over E, (where q 2 p2, p a prime power) with two matrices joined by an
edge if and only if their difference has rank 1. (see [17, section 95])

The alternating forms graphs Alt(n, q) (where n,q > 1) have as vertices the n X n
alternating matrices over Fq , that is, all n x n matrices (a,,),,xn with a,,— = —a,-,-, for
l S i, j S n, and a,-,- = 0 for all i, with two matrices joined by an edge if and only if their
difference has rank 1. (see [17, section 95])

Now let us consider the general classiﬁcation scheme for the primitive DTGs of afﬁne
type. Let G be an afﬁne DTG with Aut(G) = A. Then V(G) can be identiﬁed with a vector
space V over the ﬁeld IF, of order s for some power 5 = r” of a prime r, maximal with respect
to A0 S GL(V), where A0 is the stabilizer in A of 0 E V. Van Bon in [10], has proved the

following result.

Theorem 3.2.1. Let A be an afﬁne primitive group acts distance-transitively on a connected

28

noncomplete graph G of valency k 2 3 and diameter d > 2. Then with s and V as above,

we have one of the following.
o (I) G is a Hamming graph H(n,q)

o (2) G is a bilinear forms graph Hq(n, d).

{3) V is I-dimensional and A0 is a subgroup of GL(I, s).

(4) The generalized Fitting subgroup K := F ‘(AO /Z (A0 ﬂ GL(V))) of the central quo-
tient Ao/Z(A0 ﬂ GL(V)) of A0 is nonabelian and simple.

In a diagram:

 

A afﬁne group
G connected noncomplete (k, d 2 3)

 

 

 

 

 

[

l

K 2: F*(A0/Z(A0 ﬂ GL(V))) V is l-dimensional
is nonabelian & simple A0 S GL(L 5)

 

 

 

 

 

 

G is H(n, g) G is Hq(n, d)

 

 

 

 

 

 

 

 

 

 

Figure 3.2: affine tree

Cohen and others have pursued Van Ben’s strategy to complete the classiﬁcation of DTGs
of afﬁne type. We will list all such possibilities of G together with the derived results.

Notice that, in cases (1) 8c (2) the graphs are fully determined.

3.2.1 The one dimensional afﬁne case

This case is completely done by Cohen, Ivanov and Alexander in [26]. They proved the

following result.

Theorem 3.2.2. Suppose that case (3) holds with n = 1 and d > 2. Then G is the Hamming

graph H(4,3) and s = 64, A0 E” Z9 )4 Z3 or Z9 )4 Z6.

29

In case (4), The classiﬁcation of ﬁnite simple groups is invoked to make a further subdi-

vision according to various types of simple group K.

(i) alternating: K E” An(n 2 5),

(ii) Lie type same characteristic:(exceptional & classical),
(iii) Lie type cross characteristic,

(

iv) sporadic case.

3.2.2 The aﬁine alternating

The affine alternating case is completed in [55] by Liebeck & Praegcr. They proved the

following result:

Theorem 3.2.3. Suppose A, s z r”, G and K are as above, with K ’5’ An for some integer
n 2 5. Then either the diameter d S 2, or G is a halved n-cube %H(n, 2), a quotient n-cube

H(n, 2) or a quotient halved n-cube H(n, 2).

l
2

3.2.3 The afﬁne groups of exceptional Lie type in same character-
istic
In this subsection, K is an exceptional Lie type group over 19“,, for some power q = r“ of r.

The affine groups of exceptional Lie type in same characteristic are dealt with in [14]. Van

Bon & Cohen proved the following result:

Theorem 3.2.4. Suppose that A, s = r”, V, G and K are as in Theorem 321(4), with
K a quasisimple group of exceptional Lie type over 11"}, for some power q = r“ of r. Then
K ’_—‘i E6(q), the universal Chevalley group of type E6 over qu, V is a 27-dimensional quK-
module (so q = s), and G is the aﬁ‘ine E5 graph (see 5.2.8 below for def.) with intersection

0

_ l2_ 9_ 2 _ 8
army 2(G) = {W, (18((14 +1)(q5 -1),q16(q -1);1,q8 + (1“, gaff}-

30

3.2.4 The afﬁne groups of classical Lie type in same characteristic

The affine groups of classical Lie type in same characteristic are handled by Van Bon, Cohen

& Cuypers[15]. They proved the following result:

Theorem 3.2.5. Suppose that A, s = r”, V, G and K are as in Theorem 321(4), with K
a classical simple group of characteristic r. Then one of the following holds, where em = —1

if m even and em = 1 otherwise.

G is the alternating forms graph and K = SL(m, s)/(em1m) or K = SL(m, r°)/(emIm)
(bla) and n = m(m —1)/2.

G is the Hermitian forms graph and K = SL(m, sZ)/(emIm) with n = m(m + l)/2.

G is the quotient cube H(9, 2) and K = PSL(2,8).

G is the halved cube %H(9, 2) and K = PSL(2,8).

3.2.5 The affine groups of Lie type of cross characteristic

The afﬁne groups of Lie type of cross characteristic are dealt with in [27]. Cohen, Magaard

and Shpectorov proved the following result:

Theorem 3.2.6. Suppose that A, s = r”, V, G and K are as in Theorem 321(4) with
K a simple group of Lie type over R, for some power q = p“ of a prime p distinct from r
and that K cannot be deﬁned as a group of Lie type over a ﬁeld of characteristic 3. If G is
not a Hamming graph, a quotient cube, a half-cube, or a quotient half-cube, then G is the
coset graph of the extended ternary Golay code with intersection array {24, 22, 20; 1, 2, 12},
full automorphism group 36.2.M12 and K g PSL(2,11).

31

3.2.6 The afﬁne sporadic groups case

This case is completely classiﬁed in [16] by Van Bon, Ivanov and Saxl. They proved the

following result:

Theorem 3.2.7. Suppose A, s, V, G and K are as in Theorem 321(4) with K a sporadic

simple group. Then G and K are described in the following table

Table 3.1: afﬁne sporadic distance-transitive graphs

EV I] array ] name ] K ]
36 {24, 22,20; 1, 2, 12} extended ternary Golay 2.M12
210 {22, 21, 20; 1, 2, 6} truncated binary Golay M22
210 {231, 160, 6; 1, 48, 210} (truncated binary Golay)2 M22
211 {23, 22, 21; 1, 2, 3} perfect Golay M23
211 {253, 210, 3; 1, 30, 231} (perfect Golay)2 M23

 

 

 

 

 

 

 

 

 

 

 

 

 

3.3 Primitive DTGs of Simple Socle Type

In this section, we discuss the present state in the classiﬁcation of primitive DTGs of simple
socle type.
The classiﬁcation of ﬁnite simple groups can be invoked to make further subdivision of
the possibilities for F *(A).
(i) Alternating groups.
(ii) Groups of Lie type.

(iii) Sporadic groups.

In a diagram:

32

 

simple socle &
its associated DTGs

 

 

 

 

 

 

 

 

 

 

[33-1] [3.3.2] [3.3.3]
alternating K 2’ An _ . ‘
n 2 5 L10 tYPG sporadic case

 

 

 

 

 

 

 

 

 

Figure 3.3: simple socle tree

3.3.1 The alternating simple socle

The main examples of graphs admitting distance—transitive action of the alternating simple
socle are the Johnson graphs J (n, k), n 2 2k and the Odd graphs 0;,
This subcase where F *(A) ’5 An(n 2 5) is dealt with in [56]. Liebeck, Praegcr and Saxl

proved the following result:

Theorem 3.3.1. Let A act primitively and distance—transitively on a graph G with valency
and diameter at least three. If F *(A) 21 A, for some n 2 5, then G is one of the following

graphs:
0 Johnson graph J(n, d) where n > 2d
0 odd graph 0;, where n = 2k — 1
o quotient Johnson graph J(2d, d) where n = 2d and d 2 4

c The complement of the quotient Johnson graphs J(8, 4) & J(IO, 5)

3.3.2 The simple socle of Lie type

This is the only open case in the classiﬁcation. The classiﬁcation is expected to follow the

pattern of PSL(n, g), which is handled in [13].

33

Here the main examples are the Grassmann graphs Jq(n, k), 1 S k < n. The group
PSL(n,q) acts distance transitively on this graph and the full automorphism group of
Jq(n, k) is PFL(n,q) if 77. # 2k and Aut(PSL(n, q)) otherwise.

Theorem 3.3.2. (Van Ban E! Cohen) Let A be a group satisfying PSL(n,q) S1 A S
Aut(PSL(n,q)) for n 2 2 and (n,q) 7é (2,2), (2,3). Suppose that A acts primitively and
distance transitively on a graph G having diameter d 2 3. Then either G is a Grassmann

graph Jq(n, k) or G is as listed in the following table.

34

Table 3.2: graphs with distance-transitive groups A such that F *(A) 2 PSL(n, q)

 

 

 

 

 

 

 

 

 

 

 

 

[ IV | A array ] name ] (n,q) ]
28 {3,2,2,1;1,1,1,2} Coxeter (2,7)
36 {5,4,2;1,1,4} Sylvester (2,9)
45 {4,2,2,2;1,1,1,2} gen. 8-gon (2,1) (2,9)
68 {12,10,3;1,3,8} Doro (2,16)
102 {3,2,2,2,1,1,1;1,1,1,1,1,1.3} Biggs-Smith (2,17)
57 {6,5,2;1,1,3} Perkel (2,19)
65 {10,6,4;l,2,5} Locally Petersen (2,25)
“iii—"19:1 {2q.q.q;l,1,2} gen- Egon ((1,1) (3a)
280 {9,8,6,3;1,1,3,8} (Her(3, 4))3 (3,4)
56 {15,8,3;1,4,9} J(8,3) (4,2)

 

 

 

 

 

 

 

We close this subsection by listing all known primitive distance—transitive graphs of di-

ameter d > 2 and simple socle of Lie type automorphism groups that are not PS L(n, q).

Table 3.3: the rest(known) DTGs with simple socle Lie type groups

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

W G ][ Aut(G) ]]
[ Dual polar graphs [Gd(q)] P2p(2d, q)
Dual polar graphs [Bd(q)] PFO(2d + 1, q)
Dual polar graphs [2Dd+1(q)] FPO-(2d + 2, q)
Dual polar graphs [2A2d(r)] PFU(2d + 1, r)
I Dual polar graphs [2Agd-1(7‘)] PI‘U (2d, r)
Dual polar graphs [210n(q)], n = 4 PFO+(2n, q)
Dual polar graphs [éDn(q)], n > 4 PFQ+(2n, q)
E7 graphs F*(Aut(G)) = E701)
unitary nonisotropics graph on 208 points PFU(3, 42)
line graph of the Hoffman-Singleton graph P2U(3, 52)
generalized hexagons (q, g) F *(Aut(G)) = G2(q)’
generalized hexagons (q, Q3), (43,61) F*(Aut(G)) = TD4(q)
generalized octagons (q, l) F*(Aut(G)) = Sp(4, q) with q = 2“
generalized octagons (q, qT), (q2, q) F‘(Aut(G)) = 2F4(q)’ with q = 2T“+1
it generalized dodecagons (q, 1) F*(Aut(G)) = G2(q) with q = 3“

 

 

35

3.3.3 The sporadic simple socle

For F *(A) sporadic simple socle, the possible graphs G are determined in [50]. Ivanov,

Linton, Lux, Saxl and Soicher have proved the following result:

Theorem 3.3.3. Let A be a primitive distance-transitive group of automorphisms of a graph
G with d 2 3 and sporadic simple generalized Fitting subgroup K. Then G and K are as

described in the following table.

Table 3.4: simple socle sporadic distance—transitive graphs

 

 

 

 

 

 

 

 

 

 

 

 

L] V l ] array ] name [ K ]
266 {11,10,6,1;1,1,5,11} Livingstone J1
315 {10,8,8,2;1,1,4,5} near octagon J2
759 {30,28,24;1,3,15} Witt M24
506 {15,14,12;1,1,9} truncated from Witt M23
330 {7,6,4,4;1,1,1,6} doubly truncated Witt M22

22880 {280,243,144,10;1,8,90,280} Patterson Suz

 

 

 

36

Chapter 4

Statement of Main Results

In this brief chapter we state the main results of this thesis. Speciﬁcally, we give in Table
4.1 a list which, we believe, contains all primitive distance-transitive graphs of diameter at
least 3, as discussed in the previous chapter. We then give, under Theorem 4.1, a second list
(Table 4.2) which, for each primitive case from Table 4.1 except one, describes all associated
imprimitive graphs.

The exceptional case is that of distance—transitive generalized 2d-gons, where we have
left open the determination of all distance—transitive antipodal covers of diameter 2d. For

bipartite imprimitive distance-transitive graphs, our results are complete.

4.1 Known Primitive Distance-Transitive Graphs of

Diameter at Least Three

In Table 4.1 below we give a list of the known distance—transitive graphs G of diameter at

least 3, as discussed in chapter 3, and some information about the group A = Aut(G).

37

Table 4.1: primitive distance-transitive graphs

 

~—- -‘1

G

 

 

 

 

 

 

 

 

 

 

 

 

] Polygons P”, n 2 6 ' D2,,
[ Johnson graphs J(n, k), n > 2k Sn
[ quotient Johnson graphs J(2k, k), k 2 6 SQ),
" odd graphs 0)., k 2 4 Sgk_1
Hamming graphs H(n, q), n > 2 Sn 2 Sq
{H(n, 2), n 2 6 2"-1.s,,
‘T quotient n-cube H(n, 2), n 2 6 2m‘1.Sm, m = [g]
quotient halved cube {H(n, 2), even 11 2 12 2"‘2.S,,
Grassmann graphs Jq(n, k), n > 21c > 4 PFL(n, q)
dual polar graphs [Gd(q)] P2p(2d, q)

 

 

 

 

dual polar graphs [Bd(q)l

Pr0(2d + 1, q)

 

dual polar graphs [2Dd+1(Q)l

PFO‘(2d + 2, q)

 

HH‘i

dual polar graphs [2A2d(r)]

PFU(2d+ l,r)

 

 

dual polar graphs PAM—1(7)]

PI‘U(2d, r)

 

halved graphs [EFD (q)], d 2 6

PFQ+(2d, q)

 

bilinear forms graphs Hq(n, d), n 2 d > 2

PI‘L(n + d, q),

 

I
i
i
l

alternating forms graphs Alt(n, q), n 2 6

IF" (1‘; PI‘L(n, q))

 

. Hermitean forms graphs Her(n, q), n > 2, q = p2

 

E7 graphs

11‘" .E(I‘L(n Mar 6 1‘.le = 1})
PM )= M: )

 

afﬁne E6 graph

FELIPEEG (q )(Aut(qu))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

extended ternary Golay 36.2.M12
. truncated Golay 21°.M22.2
,] distance 2 graph of truncated Golay 21°.M22.2
] perfect Golay 211.M23
ll distance 2 graph of perfect Golay 1 211.M23
[] Coxeter graph PSL(2, 7).2
F Sylvester graph Aut(Sﬁ)
] Doro graph PSL(2, 16)
,] Biggs-Smith graph PSL(2,17)
] Perkel graph PSL(2, 19)
[ Locally Petersen graph PSL(2,2 5.) 2

(Her(3, 4))3 PFL(3, 4).2
) unitary nonisotropics graph on 208 points PF U (3 2)
] line graph of the Hoffman-Singleton graph PEU (3 52)
Livingstone graph J1

[. Hall-Janko near octagon AUt(J2)
[ Witt M24

 

 

 

38

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G ] A
truncated from Witt TA!”

doubly truncated from Witt A122
, Patterson graph 1 Suz
[1 generalized hexagons (q, 1) T] F‘(A) = PSL(3, q)
] generalized hexagons (q, q) ]] F‘(A) ——— G2(q)’
: generalized hexagons (q, q3), (q3, q) 1 F‘(A) = 3D4(q)

generalized octagons (q, 1) Y F‘(A) = Sp(4, q) with q = 2“

generalized octagons (q, q2), (q2, q) F*(A) 2: 2F4(q)’ with q = 22“+1

] generalized dodecagons (q, 1) i F *(A) = G2(q) with q = 3“

 

 

 

 

4.2 Covers and Doubles

Theorem 4.2.1. For each graph G in Table 4.1 above, Table 4.2 below lists all distance-
transitive imprimitive graphs that are antipodal covers of G and all distance-transitive bipar-
tite graphs that have G as their halved graph.

The only case not covered is that of diameter 2d, distance-transitive, antipodal covers of

generalized 2d - gons.

In the following table, all (known) primitive distance-transitive graphs of diameter at least
3 are presented in the ﬁrst column. In the second (ﬁfth) column, it is indicated whether the
graph G has antipodal (bipartite) distance-transitive covers (doubles) or not. If no covers
(doubles) exist we write none. If such a cover (double) exists we write it down. Moreover,
if this is the only cover (double), we write only in front of such a cover (double). In the
third (sixth) column we give the section number where such a detail about the existence
and uniqueness of the covers (doubles) can be found. In the fourth (seventh) column we

give the reference where such information was found. Our main works are indicated by ’-’ in

39

the reference column. That means the conclusions of such covers (doubles) are completely
derived and proved in this thesis. The only remain unsolve problem is ﬁnding the antipodal
distance-transitive covers of even diameter of the generalized 2d—gons (if any exists). We

used the question sign (7) for this case in the table.

Table 4.2: associated imprimitive distance-transitive graphs

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

][ G Antipodal cov- Sec. Ref, Bipartite dou~ Sec. Ref.
_[ ers bles

[] Pu, n 2 6 Only P2,, ] 5.1 — Only P2,, 6.2.1 [44]
'i J(n,d), n > 2d > 6 None ' 5.2.1 [12] Only 2.0,, 6.2.2 [43]
‘1 7(2d, d) d 2 6 Only J(2d, d) 5.2.1 [12] None 6.2.3 [44]
[ 0.,+1 Only 2.0,,+1 5.2.2 :12] None 6.2.4 :44]
] H(n,q), n > 2 None 5.2.3 :12] None 6.2.5 :43]
] %H(n, 2), n 2 6 None 5.2.3 :12] Only H(n, 2) 6.2.5 :44]
[i H(n, 2), n z 6 Only H(n, 2) 5.2.3 [12] None 6.2.6 [44]
[L éH—(n, 2), even n 2 12 Only %H(n, 2) 5.2.3 [12] Only H(n, 2) 6.2.6 [44]
[l Jq(n, d), n > 2d None 5.2.4 [12] O21)y2.Jq(2d—i~ 6.2.7 [44]
[[ dual polar graphs, d 2 3 None 5.2.5 [12: None 6.2.8 [44]
[] [llDd(q)], d = 6 or d = 7 None 5.2.5 :12: Only :Dd(q)‘ 6.2.8 -

1]] [ﬁDd(q)], d 2 8 None 5.2.5 :12] Only [Dd(q) 6.2.8 [44]
[P Hq(n, d), n 2 d > 2 None 5.2.6A :12] None 6.2.9 :44:
[ Alt(n, q), n 2 6 None 5.2.6B :12 None 6.2.10 :44;
1] Her(n,q), n 2 3 &q = p2 Only 12- and 5.2.6C {12] None 6.2.11 :44]
]] l4-covers of di- &

[] ameter 6 when [17]

][ n = 3 & q =2 4

[1 E7 graphs None 5.2.7 [12] None 6.3.2K -

]T afﬁne E6 graph None 5.2.8 [12: None 6.3.2L -

[] extended ternary Golay None 5.3.2 [12: None 6.3.1A -

[[ truncated Golay Only short- 5.3.3B - None 6.3.1B -

[i ened binary

]] Golay code &

[1 its double

 

 

 

 

 

 

 

 

 

 

 

 

 

40

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[ G Antipodal ] Sec. Ref.I Bipartite Sec. Ref.
] covers 1 I doubles
]] (truncated Golay)2 ] None TIT5.3.3CI - T Only double I 6.3.1C -
l of truncated
][ Golay
[[ perfect Golay Only its [ 5.3.3D — None 6.3.1D - I“
[] double ] ;
[I] (perfect Golay)2 None I 5 3.3E - Only double 6.3.1E - I
] of binary Go—
] . I lay if
] Coxeter graph ] None l 5.3.4A - None 6.3.2A -
[I Sylvester graph ] None I] 5.3.4B - None 6.3.2E -
HI Doro graph I None [I 5.3.4C - None 6.3.2C -
.1 Biggs-Smith graph None I 5.3.4D — None 6.3.2D -
H Perkel graph None 5.3.4B — None 6.3.2E —
[ Locally Petersen graph ] None ] 5.3.4F - None 6.3.2F -
] (Her(3,4))3 I None . 5.3.4C - - None 6.3.2C -
I unitary nonisotropics None I 5.3.41 I - None 6.3.21 -
graph on 208 points
I line graph of the None 5.3.4J - None 6.3.2J ] -
I Hoffman-Singleton
[awh
[I] Livingstone graph None . 5.3.5A - None 6.3.3A -
[I Hall-Janko near octagon None I 53.58 - None 6.3.3B -
1, Witt None 5.3.1 . [12] None 6.3.3C] - ]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

41

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G Antipodal covers ] See. Ref. Bipartite Sec. Ref.

l ] , doubles

truncated from Witt None 5.3.1 [51] None 6.3.3D -
] doubly truncated from Witt Only Faradjev— 5.3.1 ] [18] None 6.3.3B -
: Ivanov-Ivanov 3- [ &
‘[ cover with diam- ] [29]
[l . cter 8 ] ] ] _
[I Patterson graph [ None I 5 3.5F[— None 6.3.3FI -
[I generalized 2d—gons (odd diameter) I 5.4 [12] None 6.4 -
[] None I
[l (even diameter) [
‘J 11 1

 

 

 

 

 

 

 

 

 

 

 

 

 

We actually prove somewhat more. In particular, in almost all cases, Table 4.2 classiﬁes
the imprimitive distance—regular graphs associated with the graphs of Table 4.1.

Also, in situations where there are diameter 2 distance-transitive graphs belonging to
the same inﬁnite family as distance-transitive graphs of larger diameter from Table 4.1, we
sometimes consider their covers as well. However, we have made no effort to cover the
distance 2 case uniformly. Although all distance—transitive graphs of diameter 2 are known
(see, for instance [54]), there are many more families and isolated examples than for larger
diameter. Also, in contrast to the general case, the complement of a distance-transitive graph
of diameter 2 is again distance-transitive of diameter 2; so imprimitive graphs associated with
both the graph and its complement must be considered.

The imprimitive distance-transitive graphs associated with primitive graphs of diameter

1 have all been classiﬁed. For distance—transitive antipodal covers of complete graphs see

42

 

 

 

[40,41], and for those of complete bipartite graphs see [49]. For distance-transitive bipartite
graphs whose halved graph is complete, sec [48]. We will have no more to say about these

C3388 .

43

 

Chapter 5

Antipodal Covers

 

 

In this chapter we prove results that, in particular, prove Theorem 4.1 in the case of antipodal
covers. For this chapter, the primary references are the book of Brouwer, Cohen, and

Neumaier [17] and the paper of Van Bon and Brouwer [12].

44

 

 

Antipodal covers of

 

 

 

 

 

 

[5.2] f ] [5.4] [5.3]

Inﬁnite families [ Generalized 2d-gons Isolated examples

1

 

 

 

 

 

 

 

 

 

F igurc 5.1: antipodal main tree

5.1 Quotient Graphs

Recall that a distance—regular graph G with diameter d is antipodal if for all distinct vertices
v, w E {u} U Gd(u), we have d(v, w) = d. The quotient graph G of G is deﬁned by taking
the ﬁbres (antipodal classes) of G as its vertices, with two such ﬁbres join by an edge in G
if they contain adjacent vertices of G. In this case, we say that G is an r-antipodal cover of
G, where r is the common cardinality of the ﬁbres (the index of G).

We can give an equivalent deﬁnition of a cover H of G using the projection map p from
V(H) to V(G). Let H be an antipodal distance-regular graph of diameter D _>_ 3 with
quotient graph G. We say that H is a cover of G if there is a map p : V(H) —> V(G) called a
covering map which is a graph morphism, i.e., preserves adjacency, and a local isomorphism,
i.e., for each vertex u of H the restriction of p to the set ui = H51(u) is bijective. Then

p'l(u), u E G is the set of ﬁbres and r = |p“1(u)| is the index of the cover.

The following result is due to Gardiner (see Proposition 4.2.2 [17] & [31]).

Proposition 5.1.1. Let G be a distance-regular graph with intersection array i(G) 2 {b0, b1, .
..,bd_1;c1,c2,...,cd} and diameter d E {2m, 2m + 1}. Then G is antipodal if and only if
b,- 2 cd_,- for i = 0, ..., d, i 7é m. In this case G is an r-antipodal cover of its quotient graph

G, where r = 1 + 7513—: Moreover, for d > 2, G is a distance-regular of diameter m with

45

intersection array

2(6) : {b0,b1,...,bm_1;C1,C2,...,C1n_1,')(CTn}

r, if d:2m ;
where 7 =

1, if d=2m+1.

The following theorem is due to Gardiner [31].

Theorem 5.1.2. Let G be a distance-regular graph of diameter d with intersection numbers
b,, c,- and suppose H is a distance regular r-antipodal cover of G of diameter D > 2. Then H
has diameter D = 2d or D = 2d+1 and i(H) = {b0, b1, ..., bd_1, riled,cd_1, ..., c1;cl, ..., cd_1,
icd, bd_1, ..., be} for even D, andi(H) 2 {b0, b1, bd_1, t(r—1), cd, cd_1, ..., c1; c1, ..., cd_1, cd, t,

bd_1, ..., b0} for odd D and some integer t.
Remarks:

0 For D even the intersection array properties implies that r | cd and r S cd/ max(cd_1, cd

— bd_1).

o For D odd the integer t satisﬁes the conditions t(r - 1) S min(bd_1, ad) and cd S t.
Clearly, given i(G), there are only ﬁnitely many possibilities for r and t, and if cd >

min(bd_1, ad), there are none.

Corollary 5.1.3. If H is an antipodal distance-regular cover of G, then H has a proper
antipodal distance-regular cover only if G( and hence H) is either a cycle, a complete graph

or a complete bipartite graph.

Proof. Let G be neither a complete nor a complete bipartite DRG of diameter d’ and
valency k’ with intersection numbers a[, b;, c2. Further, let H be an antipodal distance—regular
cover of G of diameter d and valency 16. Let a,, b,, c,- denote the intersection numbers of H.

The intersection array of H is given in terms of that of G (see Theorem 5.1.2 above). In

46

particular, c’1 = l = bd_1. Now, suppose that K is an r-antipodal cover of H with diameter
D. The intersection array of K is given in terms of that of H and the integer r. If D is
even, then bd_1 = 1 implies that r = 2 and 1 = cd/2 = cd_1 = 2 c1 = 1. But if H is
an antipodal graph, then cd = b0 :- k = 2, and so H is a cycle graph. If D is odd, then

1 = bd_1 2 cd = k, which is impossible. I

Corollary 5.1.4. For an r-antipodal distance-regular cover of a graph G of valency k to

exist, the index r is at most It.

Now let us consider the reconstruction problem by which an antipodal graph is obtained
from its quotient graph.

Van Bon proved the following geometric criteria that are necessary conditions for the
existence of antipodal cover of DRGS (see sec. 2 [47]). In what follows, if u, v E V(G) with

d(u, v) = d, then G(u, v) is the union of all geodesics between u and v.

Proposition 5.1.5. Suppose that G is distance-regular graph of diameter d 2 2 and has an
r-antipodal distance-regular cover of diameter 2d. Then for any two vertices u, v in G with

d(u, v) = d, the subgraph induced by G(u, v) \ {u,v} = Ud_l(G,-(u) ﬂ Gd_j(v)) in G is the

i=1

disjoint union of r subgraphs of equal size.

Proof. Let H be an r-antipodal distance-regular cover of diameter 2d of G, with covering
map p: H —+ G. Let u; E p‘1(u), and let p‘1(v) :2 {v1, ...,i),}. Let C,- be the union of all
geodesics in Hbetween u] and v,(1 S j S r) and C = U]. C, (uh/v31). Then p [0: C —> C(u, v)

is an isomorphism.

Proposition 5.1.6. (see Proposition 4.2.8 [17]) Suppose that G is a distance-regular graph
of diameter d 2 2 and has an r-antipodal distance-regular cover of diameter 2d + 1. Let u, v
be vertices ofG with d(u, v) = d, and put E = {v} U {G(v) ﬂ Gd(u)}. Then the collection of

sets C(u, w) \ {u, w}(w E E) can be partitioned into r nonempty parts such that sets from

47

diﬁerent parts are disjoint, and all edges joining vertices in diﬂerent parts are contained in

G(u).

Thus the problem of ﬁnding antipodal covers of a given DRG is related to the study of
the structure of geodesics joining the vertices at maximal distance.
A near polygon is a connected graph G of diameter d 2 2 with the following two

properties:
0 There are no induced subgraphs of the shape K 1,1,2

0 If u E V(G) and L is a singular line with d(u, L) < d, then there is a unique point on

L nearest to u

Such a graph is also called a near (2d+1)-gon if there is a point at distance d from some

singular line and a near (2d)-gon otherwise.

Corollary 5.1.7. If d 2 2, and any two adjacent vertices v,w in Gd(u) have a common
neighbour in Gd_1(u), then G have no antipodal distance-regular covers of diameter 2d + 1.

In particular, this holds for the collinearity graph of a regular near 2d-gon.

Proof. Clearly, if G(v) ﬂ G(w) ﬂ Gd._1(u) 74 0, then G(u, v) \ {u, v} and C(u, w) \ {u, w}
are not disjoint. But if G is a near 2d—gon, and vw is an edge in Gd(u), then by deﬁnition of

regular near 2d—gon, the line containing vw has a (unique) point in Gd-1(u).

Corollary 5.1.8. If (1 2 2 and for any two adjacent vertices v,w in Gd(u) there is a point
in G(u) ﬂ Gd_1(v) ﬂ Gd_1(w), then G has no antipodal distance-regular cover of diameter
2d + 1. Similarly, if d 2 3 and for any two vertices u, v at distance d and any two vertices
x. y E G(v)ﬂGd_1(u) there is a vertex w E G(u)ﬂGd_2(x)ﬂGd_2(y), then G has no antipodal

distance-regular covers of diameter 2d.

48

Trivially, bipartite graphs have no antipodal distance-regular covers of odd diameter. As
was already remarked, antipodal graphs of diameter d 2 3 have no antipodal distance-regular
covers.

Given a distance-regular graph G with diameter d and parameters a,, b,-, c, and 16,, its

intersection matrix B is the tridiagonal (d + 1) x (d + 1) matrix

(01: )

1 0.1 D}
C2 (12
C3

bd-l

\ 111/

We shall say that a vector x = [2:0, 2:1, ..., xn]t is standard when x0 = 1.

 

 

Theorem 5.1.9. ( see Theorem 2.4.5 [53]) Let u 2 [ul, U2, ..., ud]’ be a standard right eigen-
vector corresponding to the eigenvalue A of B. Then the multiplicity of the eigenvalue A of

a distance-regular graph with diameter d and n vertices is

11111 = r—

We close this section by proving the well-known result that the only antipodal distance-

transitive cover of the polygon P" with n 2 6 is P2".

Proposition 5.1.10. The only antipodal distance-transitive cover of the polygon P”, n 2 6,

7:3 P2”.

Proof. Case(l) n is even, the conclusion follows from corollary 5.1.3 above.
Case(2) n 2 7 is odd. Let H be an r-antipodal cover of P", n = 2d+ 1, of diameter D. Then

by 5.1.2, either D = 2d and in this casei(H) = {2, 1,..., 1, 111(1), 1,..., 1; 1,...,1 l(1),1,...,1,

r ’ r

49

2} or D = 2d + l and i(H) : {2, 1, ..., 1, t(r — 1),1,...,1;1,...,1,1,t,1,...,2}.

(1) D = 2d. By the remarks of 5.1.2, r|1 and r S m(i1——1)' Thus the only possibility is
r = 1. Hence no such a cover exists.

(2) D = 2d + 1. By the remarks of 5.1.2, t(r — 1) S min(l, 1) and 1 S t. Thus the only
possibility is t = 1 and r = 2. Hence i(H) : {2,1,...,1,1,1,...,1;1,...,1,1,1,1,...,2} which

is uniquely determined by the polygon P20 = P2”. It is distance-transitive. Hence the only

antipodal distance-transitive double of Pn is P2". I

5.2 Inﬁnite Families

In this section we discuss all distance-transitive antipodal covers of examples belonging to
inﬁnite families (with the exception of the generalized 2d-gons). These are essentially those
examples with classical parameters. This case is handled by Van Bon and Brouwer [12] (see
also Terwilliger [68]). In those cases where Van Bon and Brouwer report results without
proof, we provide the corresponding proofs.

We shall say that a distance-regular graph has classical parameters (d, b, a, B) if its
diameter is d and its intersection array parameters can be expressed in terms of the diameter

d and three other parameters b, 61,6 as follows:

d i 2
b1:( _ )(IB—a )1
1 1 1
i i—l
c,= (1+0: )
1 1

for i = 0, ...,d, where

. l—l i— i -
i = [1,20 ,—_§ 2 (,) 1f b=1,
z {1;}, ﬁ if b 74 1.

are the Gaussian binomial coefﬁcients with basis b i.e., the number of l-dimensional
subspaces of an i-dimensional vector space over lFb. Using the above two formulas, one can

write the valency k and a,- in terms of the d, b, a, S as well:

For a given graph G, we deﬁne its double G as the graph whose vertices are the symbols
u+,u“ (u E G) where two vertices u",v" are adjacent whenever u ~ v and a 75 r. Then
clearly G is bipartite.

The following tree gives an overall picture of the current section.

 

Antipodal covers of

 

 

 

 

 

 

 

 

 

 

 

 

 

 

]
Johnson Graphs odd Graphs ] [Hamming graphs Grassmann graphs
l

l a

 

 

 

 

 

 

 

 

 

 

 

 

 

 

dual polar graphs sesquilinear forms graphs afﬁne E6 graph E7 graphs

 

 

Figure 5.2: antipodal covers of classical DTGs tree

5.2.1 Johnson graphs

Recall that the Johnson graphs J (n, k) (where 1 S k < n) have as vertices the k-subsets of

an n-set, with two k—subsets adjacent if and only if they intersect in exactly k — 1 elements.

The Johnson graphs J (n, 2) are sometimes known as Triangular graphs and also denoted
by T(n), and the Johnson graphs J (n,3) are sometimes known as Tetrahedral graphs.
The Johnson graph J (n, k) is distance-transitive graph with diameter d = min(k, n — k) and

intersection array
i(J(n, k)) = {k(n — k), (k — i)(n — k — i), ...; 12, ..., i2, ...,}

Lemma 5.2.1. (see sec 9.1 [17]) J(n,k) E” J(n,n — k), for n 2 k. Moreover, for u,v E

J(n,/c), d(u,v) = m if and only if|uﬂv = k — m.

 

Examples

1. J (4, 2) is the line graph L(K4) of the complete graph K4. It is strongly regular with
vertex set V = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}. It is isomorphic to the oc-

tahedron and has intersection array i = {4, 1; 1, 4}.

2. J (5, 2) is the line graph L(K5) of the complete graph K 5. It is strongly regular with

vertex set V = {{l,2},{1,3}, {1,4},{1,5},{2,3},{2,4} ,{2,5},{3,4},{3,5},{4,5}}.

It has intersection array i = {6, 2; 1, 4}.

3. J (6, 3) is the ﬁrst Johnson graph with diameter three. It has 20 vertices and 90 edges

with intersection array i = {9, 4, 1; 1, 4, 9}.

Proposition 5.2.2. (see sec. 4 [12]) For n 2 2d 2 6, The Johnson graph J(n, d) has no

antipodal distance-regular covers.

Proof. Let u,v E V(J(n,d)) with d(u,v) = d, and pick any two distinct vertices
x, y E G(u)ﬂGd_1(v). By lemma 5.2.1, we have |uﬂv] = d—d = 0 and [uﬂx] = [uﬂy] = d—I.
Without loss of generality, we may write u, v and x as u = {u1, U2, ..., ud}, v 2 {v1, v2, ..., vd}
and x = {u1,u2, ...,ud_1,v,~} for some i E {1, ...,d}, where the u,- and v,- arc all distinct. So,

we must have one of the following possibilities for y:

52

(i) y = u1,u2, ...,ud_1,v1 for some j E 1,...,i—1,i+ 1,...,d ;
J
(ii) y = {u1,u2, ...,u,_1,uj+1, ...,ud-1,ud,v,} for some j E {1, ...,d};

(iii) y = {u1,u2, ..., uj_1,u,-+1, ...,ud_1,ud,vk} for some 16 # i,j E {1, ..., d};

In cases (i) & (ii), x and y are adjacent vertices. In case(iii), the vertex 2 = {u1, u2, ..., uJ-__1,
21,-+1, ...,ud_1,ud,v,~} is a common neighbor of x and y in G(u) ﬂ Gd_1(v). Hence G(u) ﬂ
Gd_1(v) = 0. So, by proposition 5.1.5, there are no antipodal distance-regular covers of even
diameter.

Similarly, let u = {'u1,u2, ..., ud} E V(J(n, d)). Suppose that v, w be two adjacent vertices
in Gd(u). Lemma 5.2.1, gives [u F) v] = [u 0 w] : d - d = 0 and [v H w] = d -— 1. Without
loss of generality, we can write v and w as v = {v1,v2, ...,vd} and w = {v1,v2, ...,vd_1,a}
where the u,, v,- and a are all distinct. Then y = {v1,v2, ...,vd-1,u,-}, for i E {1,2, ...,d}, is
a common neighbor of v and w in Gd_1(u), so that by corollary 5.1.7 there are no antipodal
distance-regular covers of odd diameter. I

The only imprimitive Johnson graphs are the graphs J (2d, d) which are antipodal. So,
we need to consider their quotients.

The p X q graph has vertex set P X Q where [P] = p, [Q] = q, and (x1,y1) is adjacent to
(x2, y2) if and only if x1 = x; or y1 = 312 (but not both). A graph H is called locally G if
for each vertex x of H the graph induced by H on the set of neighbors of x is isomorphic to
the graph G.

Let us denote by [i(x, y) (where x and y are two vertices at distance 2 in a graph G) the
graph induced on the set of common neighbors of x and y; we shall call subgraphs of G of

this form p-graphs.

Proposition 5.2.3. (see pg. 147 [12]) For d 2 4, the only antipodal distance-regular cover

of the quotient Johnson graph J(2d, d) is the Johnson graph J (2d, d).

53

 

-A-_-! I

Proof. Let H be an antipodal distance-regular cover of G, with covering map p : H -—+
G. G is locally d X d and the connected components of each p-graph of G are 4-cycles
(see Theorem 1 [9]). Since p is a graph morphism, i.e., preserves adjacency, and a local
isomorphism, i.e., for each u of H the restriction of p to the set ui = H_<_l(u) is bijective,
then H must be locally d X d and the connected components of each p-graph of H are
4-cycles. Hence H is a Johnson graph (see Theorem 1 [9]). I

The Johnson graphs J(n,2) :2 T(n) and the quotient graphs J(8,4) and J(IO, 5) are
strongly regular, and their complementary graphs are also strongly regular. The graph T(5),
the complement of T(5), is the Petersen graph and will be treated next subsection. The
complement of the quotient graph 7(8, 4) is the Grassmann graph of the lines in PG(3, 2),
and we will see below that no antipodal covers exist. The complement of the quotient graph

7(10, 5) has no feasible parameters and so no antipodal covers exist.

Proposition 5.2.4. (see Proposition 4.2 [12]) The complement graphs T(n) of T(n) have no
distance-regular covers for n 2 8. There is a unique 3-antipodal distance transitive cover with

45 vertices and diameter 4 of T(6). Also, there is a unique 3-antipodal distance transitive

cover with 63 vertices and diameter 4 of T(7).

5.2.2 Odd graphs

Recall that the odd graphs 0), (k 2 2) have the (k — 1)-subsets of a (2k — 1)-set as vertices,
with two (k— 1)-subsets joined by an edge if and only if they disjoint. 0k is distance-transitive

graph with valency k, diameter d = k — 1 and intersection array
non={nk—Lk—ngaw41gk+nnnw,gt—ngw—1n
for 1: odd, and

nog={ak—Lk—Lu,k+1gk+nnrmgk—L§t—u

1
2

54

 

_ ...- -l’YLIJkM'1 ‘ ' '

for It even.

Proposition 5.2.5. For m 2 0 and u, v E Ok, we have
1. d(u,v) = 2m if and only if ]u F) v] = (k — I) — m.
2. d(u, v) = 2m +1 if and only if [u H v] = m.

Proposition 5.2.6. (see Proposition 4.1 [12]) The double odd graphs 2O,c are the only an-
tipodal distance-regular covers of O), for k 2 4, and they are distance-transitive. The Petersen
graph 03 has two antipodal distance-transitive covers, namely its double 5;,(sometimes called

the Desargues graph) and the dodecahedron.

5.2.3 Hamming graphs

Recall that the Hamming graph H (n, q) has the set of all n-tuples from an alphabet of q
symbols as its vertex set, where two n-tuples are adjacent when they differ in exactly one
coordinate. The Hamming graph is distance-transitive with diameter d =: n and intersection

array

i(H(n,q)) = {n,(q — l), (n — l)(q — 1),...,1(q — 1); 1,2, ....,n}

Proposition 5.2.7. (see Proposition 5.1 [12]) The Hamming graph H(n, q) with n > 2 has

no antipodal distance-regular covers.

The only imprimitive Hamming graphs are the n—cubes H (n, 2) which are both bipartite

and antipodal. So, we need to consider their quotient and halved graphs.

Proposition 5.2.8. (see Proposition 5.2 [12]) The only antipodal distance-regular cover of

the quotient n-cube H(n, 2) with n 2 6 is the n-cube H(n, 2), and it is distance-transitive.

The only antipodal distance-transitive covers of the quotient 4-cube are the 4-cube and
a unique cover with intersection array {4,3,3,1;1,1,3,4}. The only antipodal distance—
transitive covers of the quotient 5- are the 5-cube and a unique cover with intersection array
{5, 4, 1, 1; 1, 1,4,5}. The quotient n—cubes are characterized by the parameters except when
n = 6. For n = 6, there are three nonisomorphic graphs but none of these has antipodal

distance—regular covers (see [12]).

Proposition 5.2.9. (see Proposition 5.3 [12]) The halved n-cube %H(n, 2) has no antipodal

distance-regular covers for n _>_ 4.

Now, if n is even, the halved graph %H (n, 2) is still antipodal. So, we need to consider

its quotient graph. In what follows, H(n, 2) will denote the quotient halved (or halved

1
2

quotient) n-cube.

Proposition 5.2.10. (see Proposition 5.3 [12]) The only antipodal distance-regular cover of

the quotient halved n-cube %H(n, 2) (even n 2 8) is %H(n, 2), and it is distance-transitive.

The Hamming graphs H (2, q) and the quotient cubes H(4, 2), H(5, 2), the halved graphs
%H(4, 2) and %H(5, 2) and the halved quotient cubes %H(8, 2) and %H(n, 2) are strongly

regular graphs. So we should consider the possible covers of their complements.

 

H (2, 2) and H(4, 2) and %H (4, 2) are disconnected and so they are no more DTGs. Next,

H(2, 3) ”E H(2, 3) and H(5, 2) E’ %H(5, 2) and %H(5, 2) ":3 H(5, 2), so these have been treated

already. Next H (2, q) with q 2 4 has cd > 2bd_1 and hence no covers exist.

 

H(s, 2) is the

1

2

alternating forms on IF 4 and we will show that no covers exist. Finally, lI-I(10, 2 has c2 > 2b1
2 2

and so no covers exist.

5.2.4 Grassmann graphs

Recall that the Grassmann graph Jq(n,k) (l S k < n), have vertices the k-dimensional

subspaces of an n—dimensional vector space over a ﬁeld qu, with two of the k—subspaces

56

 

19.0.1... -

joined by an edge if and only if they intersect in a subspace of dimension [6 — l. Jq(n, k) is

distance-transitive with diameter d = min(k, n —— k).
Lemma 5.2.11. (see sec 9.3 [17]) For n 2 k, we have Jq(n, k) '5 Jq(n,n — k).
Thus we usually assume that n 2 2k and so, d = k.

Proposition 5.2.12. (see Proposition 6.1 [12]) The Grassmann graphs of diameter at least

2 have no antipodal distance-regular covers.

The only strongly regular Grassmann graphs are Jq(n,2). No covers exist for their
complements except when n = 3, where the complement is actually the quotient Johnson
graph J(_8,—4) which has the unique cover J (8, 4).

Let V be a (2d + 1)-dimensional vector space over GF(q) The doubled Grassmann
graph 2Jq(2d + 1, d) is the graph G whose vertices are the (k)-subspaces and d+1-subspaces

of V, where distinct vertices u, v are joined if and only if u C v or v C u.

Proposition 5.2.13. (see Proposition 6. 2, [12]) The double Grassmann graphs 2Jq(2d+1, d)

of diameter at least 2 have no antipodal distance-regular covers.

5.2.5 Dual polar graphs

Let V be one of the following spaces equipped with a speciﬁed form with q a prime power.
[Sp(2d, q)] :2 [Gd(q)] 2 IF 3‘1 with a nondegenerate syrnplectic form;

[Q(2d + 1, q)] z: [Bd(q)] = IFS"+1 with a nondegenerate quadratic form;

[Q+(2d, q)] :2 [Dd(q)] z Ing with a nondegenerate quadratic form of (maximal) Witt index
d;

[fl—(2d+ 2, q)] :2 [2Dd+1(q)] -—- Ing+2 with a nondegenerate quadratic form of (non-maximal)

Witt index (I;

57

 

[U (2d + 1, r)] :2 [2A2d(r)] 2 IF 3"“ with a nondegenerate Hermitean form (q = r2);
[U (2d, r)] :2 [2A2d_1(r)] 2 IF? with a nondegenerate Hermitean form (q = r2);

A subspace of V is called totally isotropic (in certain cases totally singular) if the form
vanishes completely on this subspace. The maximal totally isotropic (singular) subspaces
here are the d-spaces of V. The dual polar graph on V has as vertex set the maximal
totally isotropic subspaces, where two vertices are joined if they meet in (d — 1)-dimensional

subspace. It has classical parameters (d, g. 0. qe) where e E {0, %, 1, g, 2}.

Proposition 5.2.14. (see Proposition 7.1 [12]) Dual polar graphs of diameter at least 3
have no antipodal distance-regular covers. For d : 2, no other covers exist except for the

complete bipartite Kq+1,q+1 and the generalized quadrangle of order (2, 2) which has a unique

3-antipodal distance transitive cover.

The dual polar graphs on [Dd(q)] are bipartite. So we need to consider their halved

graphs élDd(q)I1

Proposition 5.2.15. (see pg. 151 [12]) The halved graph %[Dd(q)] of diameterm = [d/2] Z

2 has no antipodal distance-regular covers.

Proof. (We shall use the terminology of the theory of near polygons, see [20] & [61].) Let
G denotes the dual polar graph [Dd(q)]. Suppose that u, v E V(Gg) with d(u, v) = m. Let
x, y E (G2)(u)ﬂ(G2)m_1(v). Choose x1,y1 E V(G) such that d(x1,x) = d(y1,y) = d(x1,u) =
d(yl, u) = 1 and d(xl, v) = d(y1,v) = 2m —— 1. Then there is a vertex w joined to x1 and y1
with d(w, v) = 2m—2 (see Theorem 2(ii) [20]). Thus x1,y1 E G(w)ﬂG2m_1(v). Hence there is
a unique quad Q containing {x1,y1, w} (see Lemma 2.14 [61]). Since all point-quad relations
are classical, then there is a unique point z E G2m_2(v) (1 Q, and z N x1,y1 (see Lemma 2.14
[61]). Thus, there is a common neighbor z of x and y in G2 with z E G2(u) ﬂ (G2)m_1(v).
Hence G2(u) ﬂ (G2)m_1(v) is connected. It follows from proposition 5.1.5 that no covers of

diameter 2m exist.

58

 

Now, let x, y be two adjacent vertices in (G2)m(u). Then x, y E G2m(u) and d(x,y) = 2
in G. Hence there is a vertex w joined to x and y with d(w,u) = 2m — 1 (see Theorem
2(ii) [20]). Let 2 E V(G) with d(w,z) = 1 and d(z,u) = 2m - 2. Then 2 ~ x,y in G2.

Further z E Ggm-2 = (G2)m_1. Hence by corollary 5.1.7 no covers of diameter 2m+1 exist. I

The six dual polar graphs with d = 2 and the halved dual polar graphs %[D4(q)] and

[D5(q)] are strongly regular graphs. However, no covers occur for any of their complements

NIH

(see sec. 7 [12]).

5.2.6 Sesquilinear forms graphs
A. Bilinear forms graphs

Recall that the bilinear forms graphs Hq(n, m) (n 2 m) have vertices the n X m matrices
over IF q, with two matrices joined by an edge if and only if their difference has rank 1. The

bilinear forms graph is distance-transitive with diameter d = m.

Proposition 5.2.16. (see Proposition 8.1 [12]) The bilinear forms graph Hq(n,d), n 2 d,

of diameter d 2 2 has no antipodal distance-regular covers.

B. Alternating forms graphs

Recall that the alternating forms graphs Alt(n, q) (n, q > 1) have vertices the nX n alternating
matrices over IFq , that is, all n X n matrices (a,,-)nxn with a,,- = —a,-,- for 1 S i,j S n, and
a,, = 0 for all i, with two matrices joined by an edge if and only if their difference has rank

1.

Proposition 5.2.17. (see Proposition 9.1 & 9.2 [12]) The alternating forms graph Alt(n, q)

on II“, with n 2 4 has no antipodal distance-regular covers.

59

 

 

The alternating forms graphs Alt(4,q) and Alt(5, q) are strongly regular. However, no
covers of their complements exist except for the alternating form graph Alt(4, 2) which has

complement isomorphic to the quotient halved 8-cube, and was treated.

C. Hermitean forms graphs

Recall that the Hermitian forms graphs H er(n, q) (n, q > 1) have vertices the n X n Hermitian
matrices over R, (where q = p2, p a prime power) with two matrices joined by an edge if and

only if their difference has rank 1.
Proposition 5.2.18. (see Propositions 10.1 8; 10.2 [12] & sec. 11.3H [17])

1. The only antipodal distance-regular covers of even diameter of the Hermitean forms
graphs with diameter at least 3 are the unique 2- and 4-covers of diameter 6 in the case

where d = 3 and q = 4, and they are distance-transitive.

2. The only antipodal distance-regular cover of odd diameter of the Hermitean forms graph
with diameter at least 2 is the 5-cube in the case where d = 2 and q = 4, and it is

distance-transitive.

The Hermitean forms graphs H er(2, q) are strongly regular. However, no covers exist for

any of their complements.

5.2.7 E7 graphs

Let G be the collinearity graph of the points in a building of type E7 deﬁned over IFq, where
the points are those objects whose residue is of type E6. Then G is classical distance-

transitive with intersection array

9_ 5_ 5_ 9—
{Q(q8+q4+llgr-Tlvqg(q4+1)%rlaql7;1.(q4+1)ir_rl,(qs+q4+ Dir—r1}

and parameters

60

 

Inlnx—ll 4.. 1. . I

(drb, 0. ﬂ) = (3, (14, [(i)lq - 11l(110)lq — 1)-

Proposition 5.2.19. (see Proposition 12.1 [12]) The collinearity graph of the points in a

ﬁnite building of type E7 (either thin or thick) has no antipodal distance-regular covers.

5.2.8 The afﬁne E6 graph

Let G be the collinearity graph of a ﬁnite thick building of type E7, and 00 a vertex of G.
Then the subgraph induced on G3(oo) is called the afﬁne E6 graph. The afﬁne E6 graph

is distance-transitive with intersection array
{—————(qI2;i)_(‘{II—”,qs(q4 +1)(q5 - 1), (116(2 — l); 1, (14((14 + 9.28%}.
Furthermore, it has classical parameters
(d,b,a, B) = (3,q",q‘1 —1,q9 — 1).

Proposition 5.2.20. (see Proposition 13.] [12]) The aﬂine E6 graph over IFq has no an-

tipodal distance-regular covers.

5.3 Isolated Examples

In this section we will discuss the antipodal distance-transitive covers of all left known
primitive distance—transitive graphs with diameter d > 2 that are not covered in the previous
section. Our conclusions are based on two steps. First, we list all feasible intersection arrays
of possible covers. Then we look for the corresponding antipodal covers, if any exists, using
the known list of all distance—transitive graphs with small number of vertices or prove the

nonexistence of such covers using distance regularity conditions.

61

 

5.3.1 Witt graphs

In this subsection, we will discuss graphs related to Witt designs. They are essentially
distance—transitive with classical parameters (see sec. 11.4 [17]). So, they are covered by
Van Bon and Brouwer [12].

The large Witt graph G is the graph with vertices the 759 blocks of a Steiner system
S (5, 8, 24), where two vertices are adjacent when they are disjoint. G is classical distance-
transitive with intersection array {30, 28, 24; 1, 3, 15}, parameters (d, b, a, B) = (3, —2, —4, 10)

and full automorphism group M24.

Proposition 5.3.1. (see Proposition 14.1 [12]) The large Witt graph has no antipodal

distance-regular covers.

The subgraph of the large Witt graph induced by the 506 blocks of S (5, 8, 24) that miss a
ﬁxed symbol is itself classical distance-transitive with intersection array {15, 14, 12; 1, 1,9},

parameters (d, b, a, B) = (3, —2, —2, 5) and full automorphism group M23.

Proposition 5.3.2. (see pg. 162 [12] & [51]) The subgraph of the large Witt graph G with

intersection array {15, 14, 12; 1,1,9} has no antipodal distance-regular covers.

Proof. Let H be an r—antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {15,14,12,"—‘r’—1(9),1,1;1,1,%(9), 12,14,15} or D = 7 and
i(H) = {15,14,12,t(r — 1),9,1,1;1,1,9,t,12, 14,15}.
Case(l) D = 6. By the remarks of 5.1.2, r] 9 and r S m. Thus we have two
possibilities of r, namely 3 and 9.
For r = 3,4(H) = {15,14,12,6,1,1;1,1,3,12,14,15} andfor r = 9, i(H) 2 {15,141,123 1, 1;
1,1,1, 12,14,15}. However, Ivanov & Shpectorov [51] showed that neither 3-covers nor 9-
covers exist .

Case(2) D = 7. Since cd 2 9 > min(bd_1, ad), no antipodal distance-regular covers of odd

diameter exist (see the remarks of 5.1.2). I

62

 

The subgraph of the large Witt graph induced by the 330 blocks of S (5, 8, 24) that miss

two ﬁxed symbol is itself distance-transitive with intersection array {7, 6, 4, 4; 1, l, 1, 6}.

Proposition 5.3.3. (see pg. 163 [12], [18] & [29]) The only antipodal distance-regular cover
of the subgraph of the large Witt graph G with intersection array {7,6,4,4;1,1,1,6} is the
Faradjev-Ivanov-Ivanov 3-cover with diameter 8, and it is distance-transitive. Moreover,

such a cover is uniquely determined by its parameters.

Proof. Let H be an r—antipodal cover of G of diameter D. Then by 5.1.2, either
D = 8 and in this case i(H) = {7,6,4,4, 1"—:—1(6),1,1,1; 1,1,1, %(6),4,4,6,7} or D = 9 and
i(H) = {7,6,4,4,t(r -— 1),6,1,1,l;1,1,1,6,t,4,4,6,7}.
Case(l) D = 8. By the remarks of 5.1.2, r[(6) and r S War—($3317 Thus we have two
possibilities of r, namely 2 and 3.
For r = 2, i(H) = {7, 6, 4, 4, 3, l, l, 1; l, 1, 1, 3, 4, 4, 6, 7}. However, Brouwer [18] showed that
no such 2—covers exist.
For r = 3, i(H) = {7,6,4,4,4,1,1,1;1,1,1,2,4,4,6,7}. Faradjev, Ivanov, and Ivanov [29]
constructed such 3-cover, and Brouwer [18] showed that this graph is uniquely determined
by its parameters.
Case(2) D = 9. Since cd 2 6 > min(bd_1, ad), no antipodal distance-regular covers of odd

diameter exist (see the remarks of 5.1.2). I

5.3.2 Golay graphs

In this subsection, we will discuss graphs related to Golay codes. They are essentially
distance-transitive with classical parameters (see sec. 11.3 [17]). So, they are covered by
Van Bon and Brouwer [12].

Let S be a set and n a natural number. A code C of length n over the alphabet S is

a subset of S". The code is called binary(ternary) when S : ng (resp, S = IF3). The

63

--'-I'-I.1 4’. q

 

elements of G are called words.

The Hamming distance dH(u, v) between two words u and v is the number of positions
in which the entries in u and v differ, dH(u, v) : [{i : u, 75 v;}[. The weight wt(u) of a word
it is its number of nonzero coordinates.

The minimum distance 6(0) of G is deﬁned as

2d+ l, 1 [C] =1;
min{dH(u,v)]u,v E G,u # v}, [C] > 1.

The number
t(C) :2 max{dH(v, C)]v E V}

is called the covering radius of G. 6(C') and t(C) are related by the inequality 6(0) S
2t(C') + 1. The code C is perfect if 6(0) 2 2t(C) + 1.

If C is a code of length n, then a truncation of C is a code of length n —— 1 obtained
by deleting a ﬁxed coordinate position; a shortening of G is a code of word length n — 1
obtained by deleting a ﬁxed position and only retaining the code words that were 0 at that
position. Conversely, the extended code is the code of length n + 1 obtained by adding an
extra coordinate so as to make the weight even.

The Golay codes are the unique codes C with minimum distance 6 in H (n, q) with
(n,q,d, [C]) = (23, 2, 7, 212), (23,28,212), (11,3, 5,36), and (12,3, 6, 36). These are called
the binary Golay code, the extended binary Golay code, the ternary Golay code

and the extended ternary Golay code.
A. The coset graph of the extended ternary Golay code

Let G be the extended ternary Golay code. The coset graph of C, denoted G(G), has

vertex set the cosets of C, where two vertices are adjacent when they contain words that are

64

 

I

at Hamming distance one. Then G(C) is classical distance-transitive with intersection ar-
ray {24, 22, 20; 1,2, 12}, parameters (d, b, a, B) = (3, —2, —3, 8) and full automorphism group

Proposition 5.3.4. (see pg. 163 [12]) The coset graph G(G) of the extended ternary Golay

code C has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of the coset graph G (G) of diameter D. Then by
5.1.2, either D = 6 and in this case i(H) = {24, 22, 20, $102), 2, 1; 1, 2, i(12), 20,22, 24} or
D = 7 and i(H) = {24,22, 20, t(r —- 1), 12, 2, 1; 1, 2, 12, t, 20, 22, 24}.

Case(l) D = 6. By the remarks of 5.1.2, r]12 and r S m. Thus we have three
possibilities of r, namely 2, 3, and 6.

For r = 2, i(H) = {24, 22,20, 6, 2, 1; 1, 2, 6, 20, 22, 24} and so, [V(H)] 2 1+ 24+ 264 + 880 +
264 + 24 + 1 = 1458. Now using the list of all feasible intersection arrays of distance-regular
graphs having diameter 6 and with at most 4096 vertices given in [17], we conclude that no
such cover exists.

For r = 3, i(H) = {24, 22, 20, 8, 2, 1; l, 2, 4, 20, 22, 24} and so, [V(H)] = l+24+264+1320+
528 + 48 + 2 = 2187. Now using the list of all feasible intersection arrays of distance-regular
graphs having diameter 6 and with at most 4096 vertices given in [17], we conclude that no
such cover exists.

For 7‘ = 6, i(H) = {24, 22, 20, 10, 2, 1; 1, 2, 2, 20, 22,24} and so, [V(H)] =1+24+264+2640+
1320+ 120+5 = 2374. N ow using the list of all feasible intersection arrays of distance-regular
graphs having diameter 6 and with at most 4096 vertices given in [17], we conclude that no
such cover exists.

Case(2) D = 7. This graph is a near hexagon, so by corollary 5.1.7 there are no covers of

odd diameter.

B. The coset graph of the doubly truncated binary code

65

 

If C is a doubly truncated binary Golay code (q = 2,n :2 21, [C] = 212), then G(C)
is distance-transitive graph on 512 vertices with intersection array {21, 20, 16; 1,2, 12}. Fur-
thermore, G(C) has classical parameters (d,b,oz,ﬁ) = (3, ——2,——3,7) and hence the same
parameters as the Hermitean forms graph with n = 3 and q 2 4. (In fact, these graphs are
isomorphic.) Thus G(C) has the coset graph of the code C (n = 21, [C] = 2”) obtained by
taking all words in the binary Golay code that start with 00 or 11 and deleting these two
coordinate positions, as a unique 2-cover. Moreover, G (C) has the coset graph of the code
C (n = 21, [C] = 21°) obtained by taking all words in the extended binary Golay code that
start with 000 or 111 and deleting these three coordinate positions, as a unique 4-cover. No

other antipodal covers exist. See Proposition 5.2.18.1.

5.3.3 Afﬁne sporadic graphs

In this subsection, we will discuss in detail the r-antipodal distance—regular covers of the

affine sporadic graphs given in Table 3.1.

A. Extended ternary Golay graph
The extended ternary Golay graph G with 36 vertices and intersection array 2( G) = {24, 22, 20;

1, 2, 12} has no antipodal distance—regular covers. (See sec. 5.3.2.)

B. Truncated binary Golay graph

Proposition 5.3.5. The only antipodal distance-regular covers of the truncated binary Golay
graph G with 210 vertices and intersection array i(G) = {22, 21, 20; 1,2,6} are its double G as
a 2-cover of diameter 6 and the coset graph of the shortened binary Golay code as a 2-cover
of diameter 7. The coset graph of the shortened binary Golay code is uniquely determined

by its parameter as a distance-regular graph. The double coset graph of the truncated Golay

66

 

code is uniquely determined by its parameters as a distance-transitive graph.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {22,21,20,’-;;1-(6),2,1;1,2,§(6),20,21,22} or D = 7 and
i(H) = {22,21,20,t(r -—1),6,2,1;1,2,6,t,20,21,22}.
Case(l) D = 6. By the remarks of 5.1.2, r[6 and r S m. Thus we have two

possibilities of r, namely 2 and 3.

For 7' = 2, i(H) = {22,21,20,3,2, 1; l, 2,3,20,21,22} and so, [V(H)] = l+22+23l+ 1540+
231 + 22 + 1 = 2048. This is the coset graph of the shortened binary Golay code. It is
distance-transitive and uniquely determined by its parameters. (see 11.3(H) [17]).

For r = 3, i(H) = {22, 21, 20, 4, 2, 1; 1, 2, 2, 20, 21, 22} and so, [V(H) =1+22+231+2310+
462 + 44 + 2 = 3072. Now using the list of all feasible intersection arrays of distance-regular
graphs having diameter 6 and with at most 4096 vertices given in [17], we conclude that no
such cover exists.

Case(2) D = 7. By the remarks of 5.1.2, t(r — 1) S min(20, l6) and 6 S t. Thus we have

the following possibilities of t and r.

 

 

 

 

 

 

 

 

 

t r t r
6I2 10 2
6 3' 11 2
7 2 12 2
7 3 l3 2
8 2 l4 2
8 3 15 2
9 2 16 2I

 

 

 

 

 

 

 

 

For r = 2 andt E {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, we have i(H) = {22, 21, 20, t, 6, 2, 1; 1, 2, 6, t,
20, 21,22} with [V(H)] = 1 + 22 + 231+ 770 + 770 + 231+ 22 + 1 = 2048. Using the list of

67

 

all feasible intersection arrays given in (ch14 [17]), we conclude that no such graphs exist.
For T = 3 and t E {6,7,8}, we have, i(H) = {22,21,20, 2t, 6, 2, 1; 1,2,6,t, 20,21,22} with
[V(H)] = 1 + 22 + 231 + 770 + 1540 + 462 + 44 + 2 = 3072. Again using the same list of all
feasible intersection array, we conclude that no such graphs exist.

For T = 2 and t = 16, we have i(H) = {22, 21, 20, 16,6, 2, 1; 1,2,6, 16, 20, 21,22} with
[V(H)] = 1 + 22 + 231 + 770 + 770 + 231 + 22 + 1 = 2048. Now using the same list of
all feasible intersection arrays of distance-regular graphs with diameter 7 and at most 4096
vertices, such a graph exists. It is the double coset graph 5 of the truncated Golay code C.
It is distance-transitive with automorphism group (210.M22.2) X 2 (see 11.3F [17]). More-
over, it is uniquely determined by its intersection array as a distance-transitive graph (see

the proof of Proposition 6.3.4 below). I.

C. Distance two graph of truncated binary Golay graph

Proposition 5.3.6. The distance two graph of truncated Golay graph G with 210 vertices and

intersection array i(G) = {231, 160, 6; 1,48, 210} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either D = 6
and in this case i(H) = {231, 160, 6, 1;—1(210),48, 1; 1,48, ;(210),6, 160,231} or D = 7 and
i(H) = {231,160,6,t(r — 1), 210,48, 1; 1,48, 210,t,6, 160,231}.

Case(l) D = 6. By the remarks of 5.1.2, r|210 and r S W. Thus no such a cover
exists.

Case(2) D = 7. Since cd 2 210 > min(6, 21) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

D. Perfect Golay graph

Proposition 5.3.7. The only antipodal distance-transitive cover of the perfect Golay graph

68

 

G with 211 vertices and intersection array i(G) z: {23,22,21; 1,2,3} is its double 5' as a

2-couer. Moreover, the double graph 5 is uniquely determined by its parameters.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {23,22,21,1;—1(3),2, 1; 1,2, %(3),21,22,23} or D = 7 and
i(H) = {23,22, 21,t(r — 1),3,2, 1; 1, 2,3,t, 21, 22,23}.
Case(l) D = 6. By the remarks of 5.1.2, r13 and r S m. Thus r = 1. Hence no

covers exist.
Case(2) D = 7. By the remarks of 5.1.2, t(r — 1) S min(21, 23 — 3) = 20 and 3 S t. Thus

we have the following possibilities of t and r.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
t r t r t r t r j t r t r
l T
3 2 9 2 15 2 3 3 9 3 l 3 5
4 2 10 2 16 2 4 10 3 4 5
5 2 11 2 17 2 5 3 3 4 5 5
6 2 12 2 18 2 6 3 4 4 3 6
7 2 13 2 19 2 7 5 4 4 6
8 2 14 2 20 2 8 3 6 4 3 7

 

 

 

 

For r = 2 and t E {3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}, we have i(H) =
{23, 22, 21, t, 3, 2, 1; 1, 2, 3, 3, t, 21, 22, 23} with |V(H)| = 1 + 23 + 253 + 1771 +1771 + 253 +
23 + 1 = 4096. Using the list of all feasible intersection arrays given in (ch14 [17]), we
conclude that no such graphs exist.

For r = 2 and t = 20, we have i(H) = {23, 22,21,20,3, 2,1;1,2,3, 20,21,22, 23} with
lV(H)| = l + 23 + 253 + 1771 + 1771 + 253 + 23 + 1 = 4096. Now using the same list
of all feasible intersection arrays of distance-regular graphs with diameter 7 and at most
4096 vertices, such a graph exists. It is the double coset graph 6: of the binary Golay code

C. It is distance—transitive with automorphism group 2“.M23.2. In addition, 6 is uniquely

69

 

 

11- 11.931...)
«s1.

.7

MAY: ﬁn‘ hm.

 

determined by its parameters (see ME [17]).
For r = t = 3, we have i(H) = {23, 22, 21, 6, 3, 2, 1; 1, 2, 3, 3, 21, 22, 23} which is ruled out by

the following divisibility condition
if a1 = 0 and c2 2 2, then c,~+1 > c, for each i Z 1 (see Theorem 2.2.5).

Similarly, for r = 4, 5, 6, 7 and t = 3, we have c3 = c4 = 3, hence they are ruled out by the
above condition.

For 7‘ = 3 and t = 4, we have i(H) =2 {23, 22, 21,8,3,2, 1; 1, 2, 3,4, 21, 22, 23} with |V(H)} =
1 + 23 + 253 + 1771 + 3542 + 506 + 46 + 2 = 6144. The eigenvalues of H are

{23, 14.02, 7, 5.5507, —1, -—1.9318, —9, —9.6386}.
The corresponding eigenvector of the second largest eigenvalue A2 = 14.02 is
[1, 0.60956, 0.34299, 0.17093, —8.5467 X 10”, —0.17150, —0.30477, —0.50001]‘

and the multiplicity (see theorem 5.1.9 above) m(/\2) =

6144
1:12+23:(0.60956)2+253*(0.34299)2+1771*(0.17093)§+3542*(—.085467)2+506*(—0.1715O)2+46*(—0.30477)2+2*(—0.50001)2

 

= 44.984, which is not an integer. Thus there is no graph with the given array.

In a similar way, all the remain cases, i.e., r = 3 and t 6 {5,6, 7,8,9, 10}, r = 4 and
t 6 {4,5,6}, r = 5 and t 6 {3,4,5} and r = 6 and t = 4 are ruled out by the calculations
of the multiplicities of their second largest eigenvalues. Hence the only antipodal distance—

transitive cover of the perfect Golay graph G is its double 5'. I

E. Distance two graph of perfect Golay graph

Proposition 5.3.8. The distance two graph of perfect Golay graph G with 211 vertices and

intersection array i(G) = {253, 210, 3; 1, 30, 231} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either D = 6
and in this case i(H) = {253,210,3, "—;—1(231),30, 1; 1,30, i(231),3,210,253} or D = 7 and

70

 

 

 

i(H) = {253, 210, 3, t(r — 1), 231, 30, 1; 1, 30, 231, t, 3, 210, 253}.
Case(l) D = 6. By the remarks of 5.1.2, r|231 and r S Wig—3173). Thus r = 1. Hence
no covers exist.

Case(2) D = 7. Since cd 2 231 > min(3, 22) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

5.3.4 Simple socle graphs of Lie type

In this subsection, we will discuss in detail the r-antipodal distance—transitive covers of the
simple socle graphs of Lie type given in Table 3.2 and Table 3.3 (with the exception of the

generalized 2d-gons).

A. Coxeter graph

Proposition 5.3.9. The Coxeter graph G with 28 vertices and intersection array i(G) =

{3, 2, 2, 1; 1, 1, 1,2} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 8 and in this case i(H) = {3,2,2,1,’—"—'r‘—1(2),1,1,1;1,1,1,%(2),1,2,2,3} or D = 9 and
i(H) = {3, 2,2,1,t(r — 1),2,1,1,1;1,1,1,2,t,1,2,2,3}.
Case(l) D = 8. By the remarks of 5.1.2, r|2 and r S _masziT)‘ Thus 2 is the only
possible value of r. Hence i(H) = {3,2,2,1,1,1,1,1;1,1,1,1,1,2,2,3}, and so |V(H)| 2
1+ 3 + 6 + 12 + 12 + 12 + 6 + 3 + 1 = 56. Now using the list of all feasible intersection arrays
of distance-regular graphs having diameter 8 and with at most 4096 vertices given in [17],
we conclude that no such cover exists.
Case(2) D = 9. Since 0,, = 2 > min(1,1) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

B. Sylvester graph

71

 

 

Proposition 5.3.10. The Sylvester graph G with 36 vertices and intersection array i(G) =

{5, 4, 2; 1, 1, 4} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {5,4,2,%(4),1,1;1,1,§(4),2,4,5} or D = 7 and i(H) =
{5, 4, 2, t(r —1),4,1,1;1,1,4,t,2,4,5}.
Case(l) D = 6. By the remarks of 5.1.2, r|4 and r S m. Thus 2 is the only possible
value of r. Hence i(H) = {5,4, 2,2, l, 1; 1, 1, 2, 2,4, 5}, and so |V(H)| 2 1+ 5 + 20 + 20 +
20 + 5 + 1 = 72. Now using the list of all feasible intersection arrays of distance-regular
graphs having diameter 6 and with at most 4096 vertices given in [17], we conclude that no
such cover exists.

Case(2) D = 7. Since ed 2 4 > min(2,1) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

C. Doro graph

Proposition 5.3.11. The Doro graph G with 68 vertices and intersection array i(G) =

{12, 10,3; 1,3,8} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {12, 10,3,5}1(8),3,1;1,3,%(8),3, 10,12} or D = 7 and
i(H) = {12, 10, 3, t(r — 1),8,3, 1; 1,3,8,t,3,10, 12}.
Case(l) D = 6. By the remarks of 5.1.2, r|8 and r S m' Thus r = 1. Hence no
cover exists.
Case(2) D = 7. Since cd = 8 > min(3, 12 —— 8) (see remarks of 5.1.2), no feasible array

exists. Hence no such cover exists. I

D. Biggs-Smith graph

72

 

Proposition 5.3.12. The Biggs-Smith graph G with 102 vertices and intersection array

i(G) = {3, 2, 2, 2, 1, 1, 1; 1,1, 1, 1, 1, l, 3} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D =14 and i(H) = {3,2,2,2,1,1,1,5;—1(3),1,1,1,1,1,1;1,1,1,1,1,1,%(3),1,1,1,2,2,2,3}
or D :15 and i(H) = {3,2,2,2,1,1,1,t(r—1),3,1,1,1,1,1,1;1,1,1,1,1,1,3,t,1,1,1,2,2,2
,3}.

Case(l) D = 14. By the remarks of 5.1.2, r|3 and r S Thus r = 1. Hence no

3
cover exists.
Case(2) D = 15. Since cd = 3 > min(1,3 — 3) (see remarks of 5.1.2), no feasible array

exists. Hence no such cover exists. I

E. Perkel graph

Proposition 5.3.13. The Perkel graph G with 57 vertices and intersection array i(G) =

{6, 5, 2; 1, 1,3} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {6,5,2, r{1(3),1,1;1, 1,;(3),2,5,6} or D = 7 and i(H) =
{6, 5, 2, t(r — 1), 3, 1, 1; 1, 1, 3, t, 2, 5, 6}.
Case(l) D = 6. By the remarks of 5.1.2, r|3 and r S m. Thus r = 3. Hence
i(H) = {6,5, 2,2, 1, 1;1,1, 1,2,5,6} and |V(H)| = 1+6+30+60+60+ 12+2 = 171. Now
using the list of all feasible intersection arrays of distance-regular graphs having diameter 6
and with at most 4096 vertices given in [17], we conclude that no such cover exists.

Case(2) D = 7. Since ed 2 3 > min(2, 6 — 3) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

F. Locally Petersen graph

73

 

-mtc‘.‘ I" I. I...‘ l ' I'

 

 

 

Proposition 5.3.14. The locally Petersen graph G with 65 vertices and intersection array

i(G) = {10, 6, 4; 1, 2, 5} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {10,6,4,L;—1(5),2,1;1,2,-}(5),4,6, 10} or D = 7 and
i(H) = {10,6,4,t(r — 1), 5, 2, 1; 1, 2, 5, t, 4, 6, 10}.
Case(l) D = 6. By the remarks of 5.1.2, r|5 and r S WET—T) Thus r = 1. Hence no
cover exists.

Case(2) D = 7. Since Cd 2 5 > min(4,10 — 5) (see remarks of 5.1.2), no feasible array

exists. Hence no such cover exists. I

G. The distance three graph (H er(3, 4));;

Proposition 5.3.15. The distance three graph G = (H er(3,4))3 of the Hermitian graph
Her(3, 4) with 280 vertices and intersection array i(G) = {9, 8, 6, 3; 1, 1,3,8} has no antipodal

distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 8 and in this case i(H) = {9,8,6,3,’—"§1-(8),3,1,1;1,1,3,§(8),3,6,8,9} or D = 9 and
i(H) = {9,8,6,3,t(r —- 1),8,3, 1, 1; 1, 1,3,8,t,3, 6,8,9}.
Case(l) D = 8. By the remarks of 5.1.2, r|8 and r S m. Thus r = 1. Hence no
cover exists.

Case(2) D = 9. Since ed 2 8 > min(3, 9 — 8) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

H. The Johnson graph J (8, 3)

The Johnson graph J (8, 3) has no antipodal distance-regular covers. (See sec. 5.2.1.)

74

 

 

I. Unitary nonisotropics graph on 208 points

Proposition 5.3.16. The unitary nonisotropics graph G with 208 vertices and intersection

array i(G) = {12, 10,5; 1, 1,8} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either

D = 6 and in this case i(H) = {12,10,5, r1(8),1,1;1,1,§(8),5, 10,12} or D = 7 and

7'

 

i(H) = {12, 10, 5, t(r —1),8,1,1;1,1,8,t,5,10,12}.

Case(l) D = 6. By the remarks of 5.1.2, r|8 and r S m. Thus 2 is the only
possible value of r. Hence i(H) = {12, 10,5,4,1,1;1, 1,4,3,5, 10,12}, and so |V(H)| =
1 + 12 + 120 + 150 + 120 + 12 + 1 = 416. Now using the list of all feasible intersection arrays
of distance-regular graphs having diameter 6 and with at most 4096 vertices given in [17],
we conclude that no such cover exists.

Case(2) D = 7. Since 0,; = 8 > min(5,4) (see remarks of 5.1.2), no feasible array exists.

Hence no such cover exists. I

J. Line graph of the Hoffman-Singleton graph

Proposition 5.3.17. The line graph of the Hoﬁrnan-Singleton graph G with 175 vertices

and intersection array i(G) = {12, 6, 5; 1, 1, 4} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 6 and in this case i(H) = {12,6,5,5:—1(4),1,1;1,1,%(4),5,6,12} or D = 7 and i(H) =
{12,6,5,t(r — 1),4,1,1;1,1,4,t,5,6,12}.
Case(l) D = 6. By the remarks of 5.1.2, r|4 and r S m. Thus we have two

possibilities of r, namely 2 and 4.
For T = 2, i(H) = {12, 6, 5, 2, 1, 1; 1, 1, 2, 5, 6, 12} with |V(H)| = 1+12+72+180+72+12+1 =
350. Now using the list of all feasible intersection arrays of distance-regular graphs having

diameter 6 and with at most 4096 vertices given in [17], we conclude that no such cover

75

 

exists.

For r = 4, i(H) = {12,6,5,3,1,1;1,1,1,5,6,12} with |V(H)| 2 1+ 12 + 72 + 360 + 216 +
36 + 3 = 700. Now using the list of all feasible intersection arrays of distance-regular graphs
having diameter 6 and with at most 4096 vertices given in [17], we conclude that no such
cover exists.

Case(2) D = 7. By the remarks of 5.1.2, t(r — 1) S min(5, 8) and 4 S t. Thus we have the

following possibilities of t and r.

 

 

 

 

 

 

 

 

For r = 2 anth {4,5}, we have i(H) = {12,6,5,t,4,1,1;l,1,4,t,5,6,12} with |V(H)| =
1 + 12 + 72 + 90 + 90 + 72 + 12 + 1 = 350. Using the list of all feasible intersection arrays

given in (ch14 [17]), we conclude that no such graphs exist. I

5.3.5 Sporadic simple socle graphs

In this subsection, we will discuss in detail the r-antipodal distance-transitive covers of the

sporadic simple socle graphs given in Table 3.4.

A. Livingstone graph

Proposition 5.3.18. The Livingstone graph G with 266 vertices and intersection array

{11, 10, 6, 1; 1, 1,5, 11} has no antipodal distance-regular covers.

Proof. Let H be an r—antipodal cover of G of diameter D. Then by 5.1.2, either D = 8
and in this case i(H) = {11,10,6,1, £;—1(11),5, 1,1;1,1,5,%(11),1,6,10,11} or D = 9 and
i(H) = {11,10,6,1,t(r —1),11,5,1,1;1,1,5,11,t,1,6,10,11}.

Case(l) D = 8. By the remarks of 5.1.2, r|11 and r S —————1—1——- Thus r = 1. Hence no

ma:1:(5,11—1)'

76

 

cover exists.
Case(2) D = 9. Since cd 2 11 > min(1,11 — 11) (see remarks of 5.1.2), no feasible array

exists. Hence no such cover exists. I

B. Hall-Janka near octagon

Proposition 5.3.19. The Hall-Janko near octagon G with 315 vertices and intersection

array {10, 8, 8, 2; 1, 1,4,5} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either
D = 8 and in this case i(H) = {10, 8, 8, 2, rfl(5),4, 1, 1; 1, 1,4, i(5), 2, 8, 8, 10} or D = 9 and
i(H) = {10,8, 8,2,t(r - 1), 5,4, 1, 1; 1, 1, 4, 5, t, 2, 8, 8, 10}.

Case(l) D = 8. By the remarks of 5.1.2, rl5 and r S Thus r :2 1. Hence no

__51__
max(4,5—2)'
cover exists.

Case(2) D = 9. Since ed : 5 > min(2, 10 — 5) (see remarks of 5.1.2), no feasible array

exists. Hence no such cover exists. I

C. Witt graph
The Witt graph with 759 vertices and intersection array {30, 28, 24; 1, 3, 15} has no antipodal

distance-regular covers. (See sec. 5.3.1.)

D. Truncated from Witt graph
The truncated Witt graph with 506 vertices and intersection array {15, 14, 12; 1, 1, 9} has no

antipodal distance-regular covers. (See sec. 5.3.1.)

E. Doubly truncated from Witt graph
The only antipodal distance-transitive cover of the doubly truncated Witt graph with 330

vertices and intersection array {7, 6, 4, 4; l, 1, 1,6} is the Faradjev—Ivanov-Ivanov 3-cover with

77

 

n‘

1

diameter 8. (See sec. 5.3.1.)

F. Patterson graph of Suz type

Proposition 5.3.20. The Patterson graph G of Suz type with 22880 vertices and intersection

array {280, 243, 144, 10; 1, 8, 90, 280} has no antipodal distance-regular covers.

Proof. Let H be an r-antipodal cover of G of diameter D. Then by 5.1.2, either D = 8
and in this case i(H) = {280, 243, 144, 10, 453—1-(280),90,8, 1; 1, 8,90, %(280),10, 144,243,280}
or D = 9 and i(H) = {280, 243, 144, 10, t(r - 1), 280, 90, 8, 1; 1, 8, 90, 280, t, 10, 144, 243, 280}.

 

Case(l) D = 8. By the remarks of 5.1.2, r|280 and r S 280 Thus r = 1. Hence

max(90.280— 10) '

no cover exists.
Case(2) D = 9. Since ed -— 280 > min(lO, 280 —— 280) (see remarks of 5.1.2), no feasible

array exists. Hence no such cover exists. I

5 .4 Generalized 2d—gons

Here our results for distance-regular covers are presently restricted to antipodal covers of
odd diameter, a case covered by Van Bon and Brouwer [12]. Speciﬁc cases, for instance the
generalized hexagon with parameters (2,1), can be handled by methods like those of the
previous section. It seems likely that for general results we will need to use the full force of
the distance-transitive assumption.

Notice that, the ﬁnite distance-transitive generalized polygons were classiﬁed by Bueken-

hout and Van Maldeghem [19].

Proposition 5.4.1. (see Corollary 2.3 [12]) The generalized 2d-gons with diameter d 2 3

have no antipodal distance-regular covers of odd diameter.

78

 

 

Chapter 6

Bipartite Doubles

 

 

In this chapter we prove results that, in particular, prove Theorem 4.1 in the case of bi-
partite imprimitive graphs. For this chapter, the primary references are the book of Brouwer,

Cohen, and Neumaier [17] and the two papers of Hemmeter [42,43].

6. 1 Halved Graphs

For an easy reference we will start this section by restating the deﬁnition of both the bipartite
double and the halved graph.

Suppose G is a bipartite distance-regular graph with diameter d. Then 02 has two

79

 

 

Bipartite doubles of

 

 

 

 

 

 

 

[6.2] [6.4] [6-31

 

 

 

Inﬁnite families Generalized 2d-gons Isolated examples

 

 

 

 

 

 

 

 

 

Figure 6.1: bipartite doubles main tree

components, and the graphs induced on these components by G2 are denoted by G+ and G ‘
(or also %G for an arbitrary one of these) and are known as the halved graphs of G. Although
they have the same parameters they need not be isomorphic. They are isomorphic if G is
a distance-transitive graph. In this case, we say that G is a bipartite distance-transitive

double (or simply a bipartite double) of its halved graph %G.

Proposition 6.1.1. (see Proposition 4.2.2 [17]) Let G be a distance-regular graph with
intersection array i(G) = {b0,b1, ...,bd_1;c1,c2, ...,cd} and diameter d 6 {2m, 2m+1}. Then
G is bipartite if and only if a,- = 0 fori = 0, ...,d. In this case, the halved graph %G is
distance-regular of diameter m with intersection array i(éG) = {bfh b’l, ...,b;n_1;c’1,c’2, ..., c'm},

where
b;=%I—::#+ifor0SiSm—1andcgzgl‘it—‘forlSjSm

Proof. We ﬁrst prove that we have a bipartite DRG if and only if all a,- are 0.

Let G be a bipartite distance—regular graph with parameters a,, b,- and c,-, with k = b0
being the valency.

First, suppose a,- 74 0 for some i. Then there are adjacent vertices v, w E G;(u). Also,
there are paths 7r, p of length i from u to v and u to w. Let a: be the last vertex where r
and p meet and let n = d(zr, v) = d(x, w). Then we can form a circuit of length 2n + 1, an

odd number. Hence G is not bipartite.

80

 

 

Conversely, suppose G is not bipartite. Then G contains some circuit C of odd length
2a + 1. Let u E G. Then there exist two adjacent vertices v, w E C such that d(u,v) =
d(u,w) = a. Hence aa 2 [G(v) ﬂ Ga(u)| Z 1.

To show that b; = b2‘:% for 0 S i S m — 1, let u,v E V(éG), u E G2;(v). Count the
number of pairs (w, z) with w E G(v) ﬂ G2;+1(u) and z E G(w) ﬂ G2;+2(u). There are b2,-
such w’ 5, each of which has b2;+1 2’s. Countng 2’ s ﬁrst, there are b; such 2’s, each of which
has c2 w’s.

To show that c;- = 2%]: for 1 S j S m, let u,v, be as above. Count the number of
pairs (w, z) with w E G(v) ﬂG2j_1(u) and z E G(v) ﬂG2j_2(u). There are cgj such w’s, each

of which has c2j_1 z’s. Counting z’s ﬁrst, there are e} such z’s, each of which has c2 w’ s. I

Now let H be a given DTG and suppose that we are interested in the bipartite distance—
transitive doubles G whose halved graph %G is H. Hemmeter[43] showed that such problem

can be reduced to the study of cliques in H.

Lemma 6.1.2. Let G be a bipartite distance-regular graph with bipartition V(G) = X U Y
and let %G be the halved graph of G having X as the set of vertices. Suppose further that

%G is not a complete graph Kn. Then for every y E Y, G(y) is a maximal clique in é-G.

MOTBOUGT, ifyl 5‘ 112, then 0011) ¢ G(3J2)-

Proof. Let y E Y. G(y) is clearly a clique of éG. Suppose it is not maximal. Let
:1: E X — G(y) and adjacent in %G to every vertex of G(y). Then 2: E G3(y) and c3 =
[G(y) ﬂ G2(a:)[ = |G(y)| = 16. So b3 2 k — c3 = 0. Hence the diameter of G is less than or
equal to 3. But this means that %G is a complete graph.

To show the last statement of the lemma, let yl 74 y2 E Y. Assume that G (yl) Q G(yg).
Then G(yl) Q G(y1)ﬂG(y2), and so k S c2. Thus 16 2 c2, and G must be complete bipartite.

But this means that %G is a complete graph, contradiction. Hence there exists an element

81

 

 

y in G(yl) that is not in G(yg) and so, G(y1)7é G(yg). I

 

So in order to reconstruct G from EEG one should ﬁnd a certain family of cliques F. Then
G has the set V = V(éG) U {f I f E F} as a vertex set. The family F must satisfy certain
preperties. For example, the cardinality of F must equal to the order of é-G and each clique
in F has the same size ls: and each vertex of %G is contained in exactly k cliques from F

where k is the valency of G.

 

Corollary 6.1.3. If H is a bipartite distance-regular double of G, then H has a bipartite

distance-regular double only if G ( and hence H ) is a cycle.

 

Proof. Suppose that K is the bipartite distance-regular double of H. Since H is a
bipartite, its maximal cliques have size 2. Then by the lemma above, the valency of K is 2.

So K is a cycle. I

6.2 Inﬁnite Families

In this section we discuss all bipartite distance-transitive doubles of examples belonging to
inﬁnite families (with the exception of the generalized 2d—gons). Most of these results are
due to Hemmeter [42,43].

The following tree gives an overall picture of the current section.

6.2. 1 Polygon

Lemma 6.2.1. (see [44]) The only bipartite distance-regular double of the polygon Pn with

n 2 6 is P2", and it is distance-transitive.

82

 

 

Bipartite double of [
J
I

 

 

 

 

 

 

 

 

[

Johnson Graphs odd Graphs Hamming graphs Grassmann graphs

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[Ldual polar graphs sesquilinear forms graphs quotient of Johnson H I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

quotient of Hamming halved of Hamming polygons l

. i‘w

 

 

 

 

 

 

 

 

Figure 6.2: bipartite doubles of large diameter DTGs tree

The ordinary polygon P" is antipodal when n is even with intersection array { 2, 1, ..., 1; 1,

1,2}. But the quotient P2,, = P", which is already handled above.

6.2.2 Johnson graphs

Theorem 6.2.2. (see Theorem 1 [43]) For n 2 2d, the only bipartite distance-regular double
of the Johnson graph J(n, d) of diameter d 2 2 is the double odd graph 2.0,; with n = 2d+ 1,

and it is distance-transitive.

6.2.3 Quotient Johnson graphs 7(2k, 19)

Theorem 6.2.3. (see Theorem 6 [44]) The Johnson quotient graph 7(2k,k) of diameter

d _>_ 2 has no bipartite distance-regular doubles.

83

6.2.4 Odd graphs

Theorem 6.2.4. (see Theorem 9 [44]) The odd graph 0;, of diameter d 2 2 has no bipartite

distance-regular doubles.

6.2.5 Hamming graphs

Theorem 6.2.5. (see Theorem 2 [43]) Let n,q 2 2. Then the Hamming graph H(n,q)
has no bipartite distance-regular doubles, except for H (2, 2) which has the graph H with
V(H) = {(i,j) : i,j E F2} U {f,-,sj : i,j E F2} where (i,j) adjacent to f,- and sj as the only

bipartite distance-transitive double.
The n—cube H (n, 2) is bipartite, and hence we need to consider its halved graph %H (n, 2).

Theorem 6.2.6. (see Theorem 14/44/) The only bipartite distance-regular double of the

halved graph %H (n, 2) with n > 4 is the n-cube H (n, 2), and it is distance-transitive.

6.2.6 Quotient Hamming graphs H(n, 2)

Theorem 6.2.7. (see Theorems 15 [44]) The quotient Hamming graph H(n,2) with n _>_ 4

has no bipartite distance-regular doubles.

Notice that the graphs H(2n, 2) is also bipartite. So, we need to consider their halved

graphs.

Theorem 6.2.8. (see Theorem 16 [44]) The only bipartite distance-regular double of the quo-

tient halved Hamming graph {H(2n, 2) with n 2 4 is H(2n, 2), and it is distance-transitive.

6.2.7 Grassmann graphs

Theorem 6.2.9. (see Theorem 8 [44]) The only bipartite distance-regular double of the

Grassmann graph Jq(n, d) with d 2 2 is the doubled Grassmann graph 2Jq(2d + 1, d), and it

84

 

 

is distance-transitive.

6.2.8 Dual polar graphs

Theorem 6.2.10. (see Theorem 11 [44]) A dual polar graph of diameter d 2 3 has no

bipartite distance-regular doubles.

Since [Dd(q)] is bipartite, we need to consider its halved graph.

Lemma 6.2.11. (see Lemma 12 [44]) Let M be a maximal clique of—é—[Dd(q)]. Then either M

is the neighborhood in [Dd(q)] of some vertex y E [Dd(q)] \ %[Dd(q)], or [M] S 2(q2+1)(q+ 1).

Proposition 6.2.12. The only bipartite distance-transitive double of the halved graph
[Dd(q)] with d = 6 or 7 is [Dd(q)].

%

Proof. Let H be a bipartite distance-regular double of the halved graph éDd(q) with
d = 6 or 7. Further, let a;, b,- and 0,- denote the parameters of H, with k = b0 being the
valency. The corresponding parameters of %[Dd(q)] will be aﬁ, b;, c: and 16’. Since c1 = 1
and b; + c; = k, we have b; = k — 1. k’ = W (see sec. 9.4 [17]). Lemma 6.1.1

(q-l)2(q+1)

with i = 0 gives c2 = {ﬁg—1). Since C2 _>_ 1, k:(k — 1) 2 19'. Using this, and assuming that

k S 2(q2 + l)(q +1), we get W S (2g3 + 2g2 + 2q + 2)(2q3 + 2g2 + 2q +1). But for
d = 6 or d = 7 last inequality gives q : 1.

So if d = 6 or d = 7, then the size of the maximal clique which appears as H (y) for
some y E Y (see lemma 6.1.2) must be larger than 2(q2 + l)(q + 1). By lemma 6.2.11, it
must be [Dd(q)] for some vertex y E [Dd(q)] \ %[Dd(q)]. There are just |V(%[Dd(q)])| of these

available, so all must be used. Thus H E [Dd(q)]. I

Theorem 6.2.13. (see Theorem 13 [44]) The only bipartite distance-transitive double of the

halved graph %Dd(q) with d > 7 is Dd(q).

85

 

6.2.9 Bilinear forms graphs

Theorem 6.2.14. (see Theorem 18 [44]) A bilinear forms graph of diameter d 2 2 has no

bipartite distance-regular doubles.

6.2.10 Alternating forms graphs

Theorem 6.2.15. (see Theorem 20 [44]) The alternating forms graph Alt(n,q) on E, with

n > 3 has no bipartite distance-regular doubles.

Notice that for n S 3, the alternating forms graphs Alt(n, q) over IF q are just the complete

graphs.

6.2.11 Hermitian forms graphs

Theorem 6.2.16. (see Theorem 21 [44]) The Hermitian forms graph of diameter d 2 2 has

no bipartite distance-regular doubles.

6.3 Isolated Examples

In this section we will discuss the bipartite distance-transitive doubles of all known primitive
distance-transitive graphs with diameter d > 2 that are not covered in the previous section.
Our conclusions are based on two steps. First, we list all feasible intersection arrays of
possible doubles. Then we look for the corresponding bipartite distance—transitive doubles if
any exist, using the known list of all distance-transitive graphs with small diameter or prove

the nonexistence of such doubles using the regularity conditions.

86

 

 

_ .- --.-..J

 

6.3.1 Afﬁne sporadic graphs

In this subsection, we discuss in detail the bipartite distance-transitive doubles of the afﬁne

sporadic graphs given in Table 3.1.

A. Extended ternary Golay graph

Proposition 6.3.1. The extended ternary Golay graph G with 729 vertices and intersection

array {24, 22, 20; 1, 2, 12} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 1458 and D = 6 or 7. However, none of the feasible intersection arrays of
the bipartite distance-regular graphs with diameter 6 or 7 and having at most 4096 vertices

(given in [17]) has 1458 vertices. Hence no such doubles exist. I

B. Truncated binary Golay graph

Proposition 6.3.2. The truncated Golay graph G with 1024 vertices and intersection array

{22, 21, 20; 1,2,6} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with parameters a;, b;, c;.
Then (6.1.1) with j = 2, gives c4 = 2C2/C3. In view of 2.2.1(3) then, c4 S 2. Thus, the only
possibilities are: c2 2 c3 = w for w = 1, 2 and c4 : 2. By 224(2), 01 = 1. Now (6.1.1) with
i = 0,1 gives 22 = bob; and 21 = b2b3. But be 2 b1 2 b2 2 b3, a contradiction. Hence no

such a double H exists. I

C. Distance two graph of truncated binary Golay graph

Lemma 6.3.3. If M is a clique of the distance 2 truncated binary Golay graph G with

[M I > 16, then, in the associated truncated binary Golay graph H *, there is a vertex with

87

 

 

A! in its neighborhood. In particular, a maximal clique of G of size bigger than 16 is the

neighborhood of some vertex in H *.

Proof. G is the distance two graph of the coset graph H * of the truncated binary Golay

code C. Using the following distance distribution diagram of H *
0 2 @ 1 2® 0 6w v = 1024 (see 11.31? [17])
—— — 16

and the properties of the truncated binary Golay code C, we will give a full description
of the vertices of H " as follow. Let M be a maximal clique of G with x := G + Q E M where
Q is the 22-tuple with 0 in all positions. Let e,- (1 S i S 22) be the 22-tuple with 1 in the
27‘" place and 0 in all other positions. We denote by x; (1 S i S 22) the 22 adjacent vertices
of x where x,- := C + 6;. Now, let e,,- be the 22-tuple with 1 in the ith and 3"" positions
and 0 elsewhere. We denote by x,,j(= x”) (i 75 j,1 S i, j S 22) the 231=(222) vertices that
are at distance two from x where xm- :2 C + e,,-. It is clear that, 551.2“ is only connected to
x,- and xj. Similarly, let em, be the 22-tuple with 1 in the it”, 3'“, and let" positions and
0 elsewhere. We denote by x3); the 770=§ (232) vertices that are at distance three from x

a,b,c

where x. . := C + em, = C + eabc. Since the words of weight 6 in the truncated binary
1,3,}: .7

Golay code C form the Steiner system S (3, 6, 22), then each triple a, b, 0 lies in exactly one

a,b,c
i,j,k

word of weight 6. It is clear that, x is only connected to x”, xix, xjyc, xmb, 113a,.” and xbﬂ.
M is composed of x and various 37M and th for i,j, k,m E {1, 2, ..., 22} where either
{i, j} and {k,m} intersect nontrivially or the 4-set {i, j, k,m} is contained in a (unique)
word ijkmpq (2 e,- + 63- + 6;, + em + 6,, + eq) of the truncated Golay code. Set Mo = M \ x.
If always {i,j} ﬂ {k,m} = (b, then [M0] S 22/2 = 11, which is not the case. So we can
assume that xij and (Eu: are in M0. Let ijkabc be the unique word of the truncated Golay

code containing {i,j, k}.

88

 

 

 

We have:
Claim: If $9,}, E M0 then either g,h E {i,j,k, a, b, c} or i E {g, h}.
In proving the claim, suppose i E {g, h}. Then the 3- or 4-sets {i,j,g, h} and {i, k,g, h} are
contained in unique codewords of weight 6. Indeed, since i, g, and h are distinct, they are
in the same codeword. But this then contains i, j, and k and so must be ijkabc. Therefore
g, h E {i,j, k, a, b, c}, completing the claim.

If, for all 2399;, E Mo, we have g, h E {i,j, k, a, b, c}, then [1110] S 15, which is not the case.
Thus, by the claim, there is x;,m E [WC with m E {i,j, k, a,b, c}. Let ijmqrs be the word of
weight 6 in the code that contains i, j, m. By the claim, for any 239,}, E M0, we must have
either g,h E {i,j, k,a, b, c} H {i,j, m,q,r,s} : {i,j} or i E {g,h}. Thus, for all xgy, E M0,
we have i E {g, h}. That is, M0 and hence All are in the neighborhood of x,- in the truncated

Golay graph, as desired. I

Proposition 6.3.4. The only bipartite distance—transitive double of the distance two graph
of truncated Golay graph G with 1024 vertices and intersection array {231, 160,6; 1,48, 210}

is the double coset graph K of truncated binary Golay code.

Proof. Let a,, b;, c,- be the parameters of the double coset graph K of truncated binary
Golay code with valency k = b0. K has distance two graph of truncated binary Golay graph
G as its halved graph. As in lemma 6.1.2, the vertex set of K has bipartition G U Y with
[G] = [Y] and each G(y), for y E Y, a maximal clique of G 2: 1K. Then by lemma 6.1.1,
c2 = 5&1). Since 0,; 2 1, k(k — 1) 2 231. Thus k 2 16. Since the valency It must be
equal to the size of the maximal clique (lemma 6.1.2), then [M] Z 16. In the other hand,
since G has smallest eigenvalue Ad 2 —-9, then the size of a clique M in G is bounded by
[AI] S 1 — f; = 26.7 (see Proposition 4.4.6 [17]). So, we have 16 S |M| S 26. But if
k e. {16, 17, 18, 19, 20, 21, 23, 24, 25, 26}, then c2 = 553% is not an integer. Hence |M| = 22.

Thus by lemma 6.3.3 above, the maximal clique M of size 22 of G is the neighborhood in the

double coset graph of truncated binary Golay code of some vertex y not in G. There are just

89

 

 

[V (G)| of these available, so all must be used. That is, if H is a bipartite distance-regular
double of G then H must be isomorphic to the double coset graph of truncated binary Golay
code K. This graph is distance-transitive (see 11.3F [17]). Moreover, since the distance two
truncated Golay graph G with 1024 vertices and intersection array {231, 160,6; 1,48, 210}
is uniquely determined by its parameters as a distance—transitive graph (see theorem 3.2.7),

then K is uniquely determined by its parameter as a distance-transitive graph. I

D. Perfect Golay graph

Proposition 6.3.5. The perfect Golay graph G with 2048 vertices and intersection array

{23, 22, 21; 1,2,3} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with parameters a,, b,, c;.
Then (6.1.1), with j = 2, gives c4 = 2c2/c3. In view of 2.2.1(3) then, c4 S 2. Thus, the only
possibilities are: c2 = c3 = w for w = 1, 2 and c4 = 2. By 224(2), 0) = 1. (6.1.1) again, with

j = 3 gives 3 = c5c6. But c6 2 c5 2 c4 = 2, a contradiction. Hence no such double exist. I

E. Distance two graph of perfect Golay graph

Proposition 6.3.6. The only bipartite distance-transitive double of distance two graph G of
perfect Golay graph with 2048 vertices and intersection array {253,210,3;1,30,231} is the

double coset graph of the binary Golay code.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 4096 and D = 6 or 7. The only feasible intersection array of bipartite DRGS
with 4096 vertices and diameter D = 6 or 7 is {23, 22, 21,20, 3, 2, l; 1, 2,3, 20, 21, 22,23} (see
ch.14 [17]). This is the parameters of the double coset graph H of the binary Golay code.

It is distance-transitive and uniquely determined by its intersection array (see 11.3153 [17]).

90

 

 

Moreover, H has G as its halved graph. Thus H is the only bipartite distance—transitive

double of G. I

6.3.2 Simple socle graphs of Lie type

In this subsection, we discuss in detail the bipartite distance—transitive doubles of the simple
socle graphs of Lie type given in Table 3.2 and Table 3.3 (with the exception of the gener-

alized 2d—gons).

A. Coxeter graph

Proposition 6.3.7. The Coxeter graph G with 28 vertices and intersection array {3, 2, 2, 1;

1, 1,1,2} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 56 and D = 8 or 9. However, none of the feasible intersection arrays of the
bipartite distance—regular graphs with diameter 8 or 9 with at most 4096 vertices (given in

[17]) has 56 vertices. Hence no such doubles exist. I

B. Sylvester graph

Proposition 6.3.8. The Sylvester graph G with 36 vertices and intersection array {5, 4, 2; 1, 1,

4} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance—regular double of G with diameter D. Then by
6.1.1, [V(H)] = 72 and D = 6 or 7. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 8 or 9 with at most 4096 vertices (given in

[17]) has 72 vertices. Hence no such doubles exist. I

C. Doro graph

91

 

 

Proposition 6.3.9. The Doro graph G with 68 vertices and intersection array {12, 10,3; 1, 3,

8} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 136 and D = 6 or 7. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 6 or 7 and at most 4096 vertices (given in

[17]) has 136 vertices. Hence no such doubles exist. I

D. Biggs-Smith graph

Proposition 6.3.10. The Biggs-Smith graph G with 102 vertices and intersection array

{3, 2, 2, 2, 1, 1, 1; 1, 1, 1, 1, 1, 1, 3} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 204 and D = 14 or 15. However, none of the feasible intersection arrays of
bipartite distance-regular graphs with diameter 14 or 15 and at most 4096 vertices (given in

[17]) has 204 vertices exists. Hence no such doubles exist. I

E. Perkel graph

Proposition 6.3.11. The Perkel graph G with 57 vertices and intersection array {6, 5, 2; 1, 1

, 3} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, [V(H)] = 114 and D = 6 or 7. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 6 or 7 and at most 4096 vertices (given in

[17]) has 114 vertices. Hence no such doubles exist. I

F. Locally Petersen graph

92

 

.. . 1‘ ' - I.
a.-.” ..

Proposition 6.3.12. The Locally Petersen graph G with 65 vertices and intersection array

{10, 6,4; 1,2,5} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, [V(H) = 130 and D = 6 or 7. However, none of the feasible intersection arrays of
the bipartite distance-regular graphs with diameter 6 or 7 (given in [17]) has 130 vertices.

Hence no such doubles exist. I

G. The distance three graph of the Hermitian graph H er(3, 4)

Proposition 6.3.13. The distance three graph G = (H er(3,4))3 of the Hermitian graph
Her(3, 4) with 280 vertices and intersection array i(G) = {9,8, 6,3; 1, 1,3,8} has no bipartite

distance-regular doubles.

Proof. Let H be a bipartite distance—regular double of G with diameter D. Then by
6.1.1, |V(H)| = 560 and D = 8 or 9. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 8 or 9 and at most 4096 vertices (given in

[17]) has 560 vertices. Hence no such doubles exist. I

H. The Johnson graph J(8,3)

J (8, 3) has no bipartite distance-regular doubles (See sec. 6.2.2).

I. Unitary nonisotropics graph on 208 points

Proposition 6.3.14. The unitary nonisotropics graph G with 208 vertices and intersection

array i(G) = {12, 10,5; 1, 1, 8} has no bipartite distance—regular doubles.

Proof. Let H be a bipartite distance—regular double of G with diameter D. Then by

6.1.1, |V(H)| = 416 and D = 6 or 7. However, none of the feasible intersection arrays of the

93

 

 

bipartite distance—regular graphs with diameter 6 or 7 and at most 4096 vertices (given in

[17]) has 416 vertices. Hence no such doubles exist. I

J. Line graph of the Hoffman-Singleton graph

Proposition 6.3.15. The line graph of the Hoﬁman-Singleton graph G with 175 vertices

and intersection array i(G) = {12, 6, 5; 1, 1,4} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 350 and D = 6 or 7. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 6 or 7 and at most 4096 vertices (given in

[17]) has 350 vertices. Hence no such doubles exist. I

K. E7 Graphs

Proposition 6.3.16. The collinearity graph of the points in a ﬁnite building of type E7 de-
ﬁned over qu with intersection array {q(q8+q4+1)9:_;11, q9(q4+1)9;_:1—1,q17; 1, (q4+1)9;__—11, (q8+

q4 + 1);;11} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of the collinearity graph G of the
points in a ﬁnite building of type E7 over qu. Further, let a;, b,- and c,- denote the param-
eters of H, with k = be being the valency. The corresponding parameters of G will be
a2, b;, c: and k’. The maximal cliques (maximal singular subspaces) of G are projective
spaces. Moreover, maximal singular subspaces should have rank equal 5 or 6. Hence lemma

6.1.2, gives k = m (the size of the maximal cliques) with n E {5,6}. Since c1 = 1 and

q—l
b; + c; = k, we have bl = k — 1. Since k’ = q(q8 + q4 + 1)9(-19—_-T1, lemma 6.1.1 with i = 0 gives

k(k-1)(q-1)

q( qg +q4 + 1) (q9_1) which is not an integer unless q = 0. Hence no such a double exists. I

Cg:

L. The afﬁne E6 Graph

94

 

 

 

Proposition 6.3.17. The aﬂ‘ine E6 graph deﬁned over IFQ with intersection array { (q q,,_1

7 (18(q4 + l)(q5 — 1), q16(q — 1); 1, q4(q4 + 1),q8%1:—__i1-} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of the affine E6 graph G deﬁned
over Fq. Further, let a;, b,- and c,- denote the parameters of H, with k = b0 being the valency.
The corresponding parameters of G will be a2, b;, c: and k’. The maximal cliques (maximal
singular subspaces) of the parapolar space E6,1(q) are projective spaces of rank equal to that
of the maximal subdiagrams of type An. Thus, of rank 4 and 5. Further, the subgraph of the
afﬁne E6(q) graph induced on (E6(q))(x) (the neighbors of x) is a (q — 1)-clique extension of
the strongly regular graph of Lie type E6,1(q) (see remark after theorem 10.8.1 [17]). Hence
the maximal cliques of the afﬁne E6(q) graph are afﬁne spaces of order q and rank n = 4 or
5. Lemma 6.1.2, gives k = q" (the size of the maximal cliques) with n E {4,5}. Since c1 = 1

and b1 + Cl: k, we have b; = q" — 1. Since 16’ = W, lemma 6.1.1 with i = 0 gives

q"(q"-1)(q“-l
(q‘2-1)(q9-1)

 

c2 = which is not an integer unless q = 0. Hence no such a double exists. I

6.3.3 Sporadic simple socle graphs

In this subsection we discuss in detail the bipartite distance-transitive doubles of the spe—

radic simple socle examples given in Table 3.4.

A. Livingstone graph

Proposition 6.3.18. The Livingstone graph G with 266 vertices and intersection array

{11, 10, 6, 1; 1, 1, 5, 11} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 532 and D = 8 or 9. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 8 or 9 and at most 4096 vertices (given in

[17]) has 532 vertices. Hence no such doubles exist. I

95

1""—1)(qg-1)

 

 

B. Hall-Janka near octagon

Proposition 6.3.19. The Hall-Janko near octagon graph G with 315 vertices and intersec-

tion array {10, 8, 8, 2; 1, 1,4,5} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, [V(H)] = 630 and D = 8 or 9. However, none of the feasible intersection arrays of
the bipartite distance—regular graphs with diameter 8 or 9 (given in [17]) has 630 vertices.

Hence no such doubles exist. I

C. Witt graph

Proposition 6.3.20. The large Witt graph with 759 vertices and intersection array {30, 28,

24; 1, 3, 15} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 1518 and D = 6 or 7. However, none of the feasible intersection arrays of
the bipartite distance-regular graphs with diameter 6 or 7 (given in [17]) has 1518 vertices.

Hence no such doubles exist. I

D. Truncated from Witt graph

Proposition 6.3.21. The truncated Witt graph with 506 vertices and intersection array

{15, 14, 12;1,1, 9} has no bipartite distance-regular doubles.

Proof Let H be a bipartite distance-regular double of G with diameter D. Then by
6.1.1, |V(H)| = 1012 and D = 6 or 7. However, none of the feasible intersection arrays of
the bipartite distance-regular graphs with diameter 6 or 7 and at most 4096 vertices (given

in [17]) has 1012 vertices. Hence no such doubles exist. I

96

 

E. Doubly truncated from Witt graph

Proposition 6.3.22. The doubly truncated Witt graph with 330 vertices and intersection

array {7, 6, 4, 4; 1, 1, 1,6} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance—regular double of G with diameter D. Then by
6.1.1, |V(H)| = 660 and D = 8 or 9. However, none of the feasible intersection arrays of the
bipartite distance-regular graphs with diameter 8 or 9 and at most 4096 vertices (given in

[17]) has 660 vertices. Hence no such doubles exist. I

F. Patterson graph of Suz type

Proposition 6.3.23. The Patterson graph G of Suz type with 22880 vertices and intersection
array {280,243,144, 10; 1, 8, 90, 280} has no bipartite distance-regular doubles.

Proof. Let H be a bipartite distance-regular double of G with parameters b;, c,-. Then
(6.1.1) with j = 2, gives c4 = 8c2/c3. In view of 2.2.1(3) then, c.; S 8. Thus, we have the

following possibilities:
1. c2 = c3 2w for w =1,2,3,4,5,6,7,8 and c4 = 8.
2. c2=l,c3=2andc4=4.
3. c2=2,c3=4andc4=4.
4. c223,c3=4andc4=6.

Case (1): By (224(2)), 0; = 1. Now (6.1.1) with i = 0,1 gives 280 = bobl and 243 = b2b3.
But b0 2 b1 2 b2 2 b3, a contradiction.
Case(2) (6.1.1) with i = 0,1 gives 280 = bobl and 243 = b2b3. But b0 2 b1 2 b2 2 b3, a

contradiction.

97

 

 

Case(3): (6.1.1) with i = 0,1 gives 560 2 bob; and 486 = b2b3. But be 2 b1 2 b2 2 b3, a
contradiction.

Case(4): (6.1.1) with i = 0,1 gives 840 2 bob; and 729 = b2b3. As b0 2 b1 2 b2 2 b3, b0 = 30,
bl = 28, b2 = b3 2 27. This contradicts b, + c,- 2 b0 for all i > 0.

Hence no such double H exists. I

6.4 Generalized 2d—gons

Here are our results are complete.

Theorem 6.4.1. Let G be the collinearity graph of a ﬁnite generalized 2d-gon with diameter
d 2 2 and parameters (3, t). Then there is a bipartite, distance-regular graph H with halved
graph G if and only if s = t. In that case, H is uniquely determined as the incidence graph
of G.

Proof. Let H be a bipartite distance—regular double of the generalized 2d-gon G of order
(s, t) and diameter d 2 2. Further, let a;, b,- and c,- denote the parameters of H, with k = be
being the valency. The corresponding parameters of G will be aﬁ, bﬁ, c: and k’. Since the
maximal cliques of the generalized 2d—gons (s, t) are K 3+1, lemma 6.1.2 gives 11: = s + 1 (the
size of the maximal cliques). Since c1 = 1 and b1+c1 = k, we have bl = 3. Since k’ = s(t+ 1),

lemma 6.1.1 with i = 0 gives c2 = [:3]

 

(1). Since c’2 = 1, lemma 6.1.1 with j = 2 gives
c4 = 1%. In view of 2.2.1(3) then, c4 S 1. Thus the only possibility is: c2 = c3 : c4 = 1
(2). (1)&(2) implies that s = t. As in lemma 6.1.2, the point set of H has bipartition G U Y
with [G] = [Y| and each G(y), for y E Y, a maximal unique of G g éH. This can only be a
line of the generalized polygon G. As 5 = t, G has the same number of points and lines. So
for every line l there is a unique y in Y with l = G (y) Thus H is the incidence graph of G,

as claimed. I

98

 

 

Corollary 6.4.2. Let G be the collinearity graph of a ﬁnite distance—transitive generalized
2d-gon with d 2 2. Then there is a bipartite, distance-transitive graph H with halved graph G
if and only if G is a generalized 4—gon of type S p4(q) with q a power of 2 or G is a generalized
hexagon of type G2(q) with q a power of 3. In both cases, H is the incidence graph ofG and

so is a generalized octagon (dodecagon) respectively.

Proof. The generalized octagon of order (1, q) and intersection array {q+ 1, q, q, q; l, 1, 1,
q+1} is distance-transitive precisely when q is a power of 2 (see sec. 6.5 [17]). The generalized
dodecagon of order (1, q) and intersection array {q+1, q, q, q, q, q; 1, 1, l, 1, 1, q+1} is distance-

transitive precisely when q is a power of 3 (see sec. 6.5 [17]). I

99

 

 

 

Bibliography

[1] Aldred, R.E.L. and CD. Godsil, Distance-regular antipodal covering graphs,
J. Combin. Th. B 45 (1988) 127-134.

[2] Araya, M., A. Hiraki, and A. Jurisic, Distance-regular graphs with b2 2 1 and
antipodal covers, Europ. J. Combin. 18 (1997) 243-248.

 

[3] Bannai, E., On distance—regular graphs with fixed valency, III, J. Alg. 107
(1987) 43-52.

 

[4] Bannai, E. and T. Ito, On distance-regular graphs with ﬁxed valency, Graphs
and Combinatorics 3 (1987) 95-109.

[5] Bannai, E. and T. Ito, On distance-regular graphs with ﬁxed valency, II,
Graphs and combinatorics 4 (1988) 219—228.

[6] Bannai, E. and T. Ito, On distance-regular graphs with ﬁxed valency, IV,
Europ. J. Combin. 10 (1989) 137-148.

[7] Biggs, N.L., A.G. Boshier, and J. Shawe—Taylor, Cubic distance-regular
graphs, J. London Math. Soc.(2) 33 (1986) 385-394.

[8] Biggs, N.L. and DH. Smith, On trivalent graphs, Bull. London Math. Soc. 3
(1971) 155-158.

[9] Blokhuis, A. and A.E. Brouwer, Locally 4-by-4 grid graphs, J. Graph Theory,
13 (1989) (2) 229-244.

[10] Ben, J. van, Afﬁne distance-transitive graphs, Thesis, Univ. Utrecht, 1990.

[11] Bon, J. van, Afﬁne distance-transitive graphs with quadratic forms, Math.
Proc. Cambridge Phil. Soc., 112 (1992) 507-517.

[12] Ben, J .T.M. van and A.E. Brouwer, The distance-regular antipodal covers of
classical distance—regular graphs, pp. 141-166 in: Colloq. Math. Soc. Janos
Bolyai, Proc. Eger 1987, 1988.

[13] Ben, J. van and A.M. Cohen, Linear groups and distance-transitive graphs,
Europ. J. Combin. 10 (1989) 399-411.

100

 

[14] Ben, J. van and A.M. Cohen, Afﬁne distance-transitive graphs and exceptional
Chevalley groups, Proc. London Math. Soc. (3) 83 (2001) 51-70.

[15] Ben, J. van, A.M. Cohen and H. Cuypers, Afﬁne distance-transitive graphs
and classical groups, March 31, 2003.

[16] Ben, J. van, A. A. Ivanov and J. Saxl, Afﬁne distance-transitive graphs with
sporadic stabilizer, Europ. J. Comb. 20 (2) (1999) 163-177.

[17] Brouwer, A. E, A.M. Cohen and A. Neumaier, Distance-regular Graphs,
Springer, Berlin, 1989.

[18] Brouwer, A. E, Uniqueness and nonexistence of some graphs related to M22,
Graphs and Combinatorics, 2 (1986) 21-29.

[19] Buekenhout, F. and H. van Maldeghem, Finite distance-transitive generalized
polygons, Geometriac Dedicata 52 (1994) 41-51.

[20] Cameron, P.J., Dual polar spaces, Geometriac Dedicata 12 (1982) 75-85.

[21] Cameron, P.J., There are only ﬁnitely many ﬁnite distance-transitive graphs
of given valency greater than two, Combinatorica 2 ( 1) (1982) 9—13.

[22] Cameron, P.J., Covers of graphs and EGQs, Discrete Math. 97 (1991) 83-92.

[23] Cameron, Peter J ., Automorphism groups of graphs, in: Selected Topics in
Graph Theory II, L.W. Beineke and R.J. Wilson (eds). Academic Press, Lon-
don, 1983, pp. 89-127.

[24] Cameron, P.J., C.E. Praeger, J. Saxl, and GM. Seitz, On the Sims conjecture
and distance-transitive graphs, Bull. London Math. Soc. 15 (1983) 499-506.

[25] Cohen, A.M., Distance-transitive graphs, Eindhoven Univ. of Technolog
(March 2001).

[26] Cohen, A.M., Ivanov, and Alexander A., Afﬁne distance-transitive groups of
dimension one, Europ. J. Combin. 21 (2000) 191-195.

[27] Cohen, A.M., K. Magaard, and S. Shpectorov, Afﬁne distance-transitive
graphs: the cross characteristic case, Europ. J. Combin. 20 (1999) 351-373.

[28] Chuvaeva, IV and D.V. Pasechnik, Distance-transitive graphs of type q.Kq,q
and projective planes, Europ. J. Combin. 11 (1990) 341-346.

[29] Faradjev, I.A, A.A. Ivanov, and AV. Ivanov, Distance-transitive graphs of
valency 5,6 and 7, Europ. J. Combin. 7 (1986) 303-319.

101

 

 

 

[30] Faradzev, LA. and A.A. Ivanov, Distance-transitive representations of groups
G with PSL2(q) S G S PFL2(q), Europ. J. Combin. 11 (1990) 347-356.

[31] Gardiner, A., Antipodal Covering Graphs, J. Combin. Th. (B) 16 (1974) 255-
273.

[32] Gardiner, A., Imprimitive distance—regular graphs and projective planes, J.
Combin. Th. (B) 16 (1974) 274-281.

[33] Gardiner, A., On trivalent graphs, J. London Math. Soc. (2), 10 (1975), 507-
512.

[34] Gardiner, A., When is an array relaised by a distance-regular graph?, pp.
209-219 in: Algebraic Methods in Graph Theory, Szeged, 1978, Vol. 1, Colloq.
Math. Soc. Janos Bolyai 25

[35] Gardiner, A., Classifying distance-transitive graphs, pp. 67-88 in: Combina-
torial Math IX, Brisbane 1981, Lecture Notes in Math. 952 (E.J. Billington,
S. Oates-Williams & A.P. Street, eds.), Springer Verlag, 1982.

[36] Gardiner, A., An elementary classiﬁcation of distance-transitive graphs of va-
lency four, Ars Combin. 19A (1985) 129-141.

[37] Gardiner, A. and Ch.E. Praegcr, Distance-transitive graphs of valency ﬁve,
Proc. Edinburgh Math Soc. (2) 30 (1987) 73—81.

[38] Gardiner, A. and CE. Praegcr, Distance-transitive graphs of valency six, Ars
Combin. 21A (1986) 195-210.

[39] Gardiner, A. and CE. Praeger, A geometrical approach to imprimitive graphs,
Proc. London Math. Soc. (3) 71 (1995) 524-546.

[40] Godsil, C .D., and AD. Hensel, Distance regular covers of the complete graph,
J. Combin. Th. B 56 (1992) 205-238.

[41] Godsil, C.D., R.A. Liebler, and GE. Praeger, Antipodal distance transitive
covers of complete graphs, Europ. J. Combin. 19 (1998) 455-478.

[42] Hall, J. I., Locally Petersen graphs, J. Graph Th., 4 (1980) 173-187.

[43] Hemmeter, J ., Halved graphs, Johnson and Hamming graphs, Utilitas Math.
25 (1984) 115-118.

[44] Hemmeter, J ., Distance-regular graphs and halved graphs, Europ. J. Combin.
7 (1986) 119-129.

[45] Hemmeter, J ., The large cliques in the graph of quadratic forms, Europ. J.
Combinatorics (1988) 9, 395-410.

102

 

ma. 9.
t
L...

 

 

[46] Ito, T., Bipartite distance-regular graphs of valency three, Lin. Alg. Appl. 46
(1982) 195-213.

[47] Ivanov, A.A., Distance-transitive graphs and their classiﬁcation, in Investiga-
tions in the Algebraic Theory of Combinatorial Objects (I. A. Faradéev, A.
A. Ivanov, M. H. Klin and A. J. Woldar, eds.), Kluwer, Dordrecht, 1994, pp.
283-378.

[48] Ivanov, A.A and A.V. Ivanov, Distance-transitive graphs of valency k, 8 S
k S 13, pp. 112-145 in: Algebraic, Extremal and Metric Combinatorics, 1986,
Cambridge Univ. Press, Cambridge, 1988.

[49] Ivanov, A.A., R. A. Liebler, T. Penttila, and CE. Praegcr, Antipodal distance-
transitive covers of complete bipartite graphs, Europ. J. Combin. 18(1997)
11-33.

[50] Ivanov, A.A., S. A. Linton, K. Lux, J. Saxl and L. H. Soicher, Distance-
transitive representations of the sporadic groups, Comm. Algebra 23 (1995)
3379-3472.

[51] Ivanov, A.A., S. V. Shpectorov, The P-geometry for M23 has no nontrivial
2—coverings, Europ. J. Comb. 11 (1990), 373-379.

[52] Jurisic, A., Distance regular antipodal covers of strongly regular graphs, Mas-
ter’s Essay, Univ. of Waterloo (April 1990).

[53] Jurisic, A., Antipodal covers, Ph. D’s Thesis, Univ. of Waterloo, (January
1995)

[54] Liebeck, M.W, The afﬁne permutation groups of rank three, Proc. London
Math. Soc. (3) 54 (1987), no.3, 477-516.

[55] Liebeck, M.W and Ch.E. Praeger, Afﬁne distance-transitive groups with al-
ternating or symmetric point stabilizer, Europ. J. Comb. 13 ( 1992) 489-501.

[56] Liebeck, M.W, Ch.E. Praeger, and J. Saxl, Distance transitive graphs with
symmetric or alternating automorphism group, Bull. Austral. Math. Soc. 35
(1987) 1-25.

[57] Praegcr, C.E., Finite transitive permutation groups and ﬁnite vertex-transitive
graphs, in Graph Symmetry (G. Hahn and G. Sabidussi, eds.), Kluwer, Dor-
drecht, 1997, pp. 277-318.

[58] Praegcr, C.E., Symmetric graphs and the classiﬁcation of the ﬁnite simple
groups, pp. 99-110 in: Groups, Proc. Conf. on combinatorial group theory,
Kyoungju, Korea, 1983, Lect. Notes Math. 1098 (AC. Kim & B.H. Neumann,
eds.), 1984.

103

 

 

 

 

[59] Praeger, C.E., Imprimitive symmetric graphs, Ars Combin. 19A (1985) 149-
163.

[60] Praegcr, C.E., J. Saxl, and K. Yokoyama, Distance transitive graphs and ﬁnite
simple groups, Proc. London Math. Soc. (3) 55 (1987) 1—21.

[61] Shult, E. and A. Yanushka, Near n-gons and line systems, Geometriae Dedi-
cata, 9 (1980), 1-72.

[62] Smith, D.H., Primitive and imprimitive graphs, Quart. J. Math. Oxford (2)
(1971) 551-557.

[63] Smith, D.H., Bounding the diameter of a distance—transitive graph, J. Combin.
Th. (B) 16, (1973) 139-144.

[64] Smith, D.H., On tetravalent graphs, J. London Math. Soc.(2) 6 ( 1973) 659-
662.

[65] Smith, A.H., Distance-transitive graphs of valency four, J. London Math.
Soc.(2) 8 (1974) 377-384.

[66] Smith, A.H., On bipartite tetravalent graphs, Discrete Math. 10 (1974) 167-
172.

[67] Taylor, D.E., T wo-graphs and doubly transitive groups, J. Combin. Th. A 61
(1992) 113-122.

[68] Terwilliger, P., P- and Q-polynomial association schemes and their antipodal
P-polynomial covers, Europ. J. Combin. 14 (1993) 355-358.

[69] Vijayan, K.S., On a class of distance transitive graphs, J. Combin. Th. (B) 25
(1978) 125-129.

[70] Weiss, R., Distance-transitive graphs and generalized polygons, Arch. Math.
45 (1985) 186-192.

[71] Weiss, R., On distance—transitive graphs, Bull. London Math. Soc. 17 (1985)
253-256. For a given k 2 3, there are, up to isomorphism, only ﬁnitely many
ﬁnite distance-transitive graphs of valency k.

[72] Yokoyama, Z., On distance transitive graphs in which the stabilizer of a point
contains an alternating group, Europ. J. Combin. 9 (1988) 379-390.

104