1.2 Operations on graphs

1.2.1     Union of graphs

The union of two graphs   has  and .  If a graph consists of k disjoint copies of a graph H, then we write .

1.2.2     Join of graphs

The join of two graphs   has   and .

1.2.3     Cartesian product of graphs

The Cartesian product of two graphs   has  and two vertices (u1,u2) and (v1,v2) of G are adjacent iff either u1 = v1 and  or u2= v2 and .

1.2.4     Walk, trail path in a graph

Let u and v be (not necessarily distinct) vertices of a graph G. A u-v walk W of G is a finite alternating sequence

of vertices and edges, beginning with vertex u and ending with vertex v, such that  for . The number k is called the length of W.

Two u-v walks  and  are equal iff  and ui = vi for  . Otherwise W1 and W2 are different.

u-v walk is closed if u = v, otherwise () it is open. A u-v trail is a u-v walk in which no edge is repeated, and a u-v path is a u-v walk in which no vertex is repeated. A path with n vertices is denoted by Pn.

A non-trivial closed trail is referred to as a circuit, and a circuit  whose vertices vi are distinct called as cycle. A cycle is even if its length is even; otherwise it is odd. A cycle of length n is an n -cycle and we denote it by Cn; a 3-cycle is also called triangle. An acyclic graph has no cycle.

In a connected graph G the distance d(u,v) between two vertices u and v is the minimum of the lengths of the u-v paths of G.

1.2.5     Connected graphs

A vertex u is said to be connected to a vertex v in a graph G if there exists a u-v path in G.

A graph is connected if every two of its vertices are connected. Otherwise the graph is disconnected.

In a connected graph G the distance  between two vertices u and v is the minimum of the lengths of the u-v paths of G.

1.2.6     Measurments in a graph

The eccentricity  of a vertex v is the number .

The radius  is the minimum eccentricity among the vertices of G, while the diameter of G  is the maximum eccentricity.

A central vertex in a graph of radius rad G is one whose eccentricity is rad G i.e. a vertex v such that .