---

Graph

---

Let V be a set and E be a collection of 2-elements subsets of V. A graph ¦£ is a pair of (V,E).
The elements of sets V and E are called vertex and edge, respectively.
Let u,v ¢º V. A path of length m connecting u and v is a sequence of the vertices ¡¡
(u= x₀,x₁,...,x_m=v) such that each (x_i,x_i+1) ¢º E.¡¡
The distance between u and v is the length of a shortest path connecting them.
A graph ¦£ is called connected if there exists a path connecting any two vertices in ¦£.

---

Distance-regular graph

---

Let ¦£=(V,E) be a graph. Let ¦£_j(u) be the set of vertices at distance i from vertex u.
For two vertices u and x in ¦£ at distance j, let

C(u,x) = ¦£_j-1(u) ¢Á ¦£₁(x)
A(u,x) = ¦£_j(u) ¢Á ¦£₁(x)
B(u,x) = ¦£_j+1(u) ¢Á ¦£₁(x).

A connected graph ¦£ is said to be distance-regular
if the size of the set C(u,x), A(u,x) and B(u,x) depend only on j rather than the choice of u and x.
In this case we write c_j a_j and b_j for the size of them. These are called intersection numbers of ¦£.

---

Distance-transitive graph

---

A permutation ¦Ò of the vertex set V of a graph ¦£ is called automorphism if (¦Ò(x),¦Ò(y)) ¢º E when never (x,y)¢º E. The set of all automorphisms of ¦£ forms a group under composition. This is called the automorphisms group of ¦£ denoted by Aut(¦£). A graph ¦£ is called distance-transitive if for any pais (w,x),(y,z) of ¦£ with the same distance there exists an automorphisms ¦Ò of ¦£ such that (¦Ò(w),¦Ò(x))=(y,z). We can see that distance-transitive graphs are distance-regular.

---

Association scheme

---

Let X be a finite set. Let R = {R₀,R₁,...,R_d} is a partition of the set X ¡ß X.
A pair (X,R) is called an association scheme of class d if the following conditions hold.
(1) R₀ = {(x,x) | x ¢º X }
(2) R_i ^T = { (y,x) | (x,y) ¢º R_i } ¢º R
(3) there are numbers p_i^t_j such that for any pair (x,y) ¢º R_t the number of elements z such that (x,z) ¢º R_i and (z,y) ¢º R_j is p_i^t_j.

Suppose ¦£ is a distance-regular graph of diameter d with vertex set V.
Let R_i = { (x,y) | at distance i } for i=0,1,...,d, and R = {R₀,R₁,...,R_d}.
Then (X,R) is an association scheme of class d.

---