1.2. BASI C DEFINITION S 5

FIGURE

7 . A small subgrap h o f the collaboratio n graph .

The degre e of a vertex u i s the numbe r o f edges incident tow . I f a graph G ha s

all its degree s equa l t o k, w e say G i s a /c-regula r graph .

DEFINITION

2 . A pat h from u to v of length t in G is an ordered sequence of

distinct vertices u = vo ,v\,..., Vt — v satisfying

fa, v

i+1

] e E{G) /o r i = 0,1, • - . , *- 1.

For example, i n the graph of Figure 7 , there is a path o f length 4 from Einstein ,

Straus, Erdos , Chun g an d Lu .

DEFINITION

3 . A walk of a graph G of length t is an ordered sequence of vertices

vo,vi,...,vt satisfying

{vi,vi+1} e E(G) for i = 0 , 1 , . . . , t - 1.

We remar k tha t vertice s i n a pat h ar e al l distinc t whil e a wal k i s allowe d t o

have repeate d vertice s an d edges .

DEFINITION 4 . For any two vertices u, v e V(G), the distanc e between u and

v, denoted by d{u,v), is the shortest length among all paths from u to v.

For example , th e distanc e betwee n Einstei n an d L u i s 3, achieved b y th e pat h

from Einstein , Straus , Graham , an d Lu .

DEFINITION 5 . A graph is connecte d if for any two vertices u and v

7

there is

a path from u to v.

DEFINITION 6. In a connected graph G, the diamete r of G is the maximum

distance over all pairs of vertices in G. If G is not connected, we use the convention

that the diameter is defined to be the maximum diameter over the diameters of all

connected components.

DEFINITION 7 . The averag e distanc e of a connected graph G is the average

taken over the distances of all pairs of vertices in G. If G is not connected, the

average distance of G is the average taken over the distances of pairs of vertices

with finite distance.

DEFINITION

8 . A directe d grap h consists of the vertex set V(G) and the edge

set E(G), where each edge is an ordered pair of vertices. We write u — + v if an edge

(u,v) is in E(G). In this case, we say u is the tail and v is the head of the edge.

Figure 8 i s a directe d grap h associate d wit h jugglin g pattern s wit h perio d 3

and a t mos t 2 balls . Fo r a n edg e fro m a verte x labelle d b y (01,02) t o a verte x