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
Previous Page Next Page