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


Two u-v walks and
are equal iff
and ui = vi for
. Otherwise W1 and W2 are
different.
A 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 .