Chapter Iv

Chapter-IV Graph Theory

Contents: 4.1

Graph

4.2

Multigraph

4.3

Complete graph

4.4

Bi Graph/Bipartite Graph

4.5

Degree

4.6

Degree Sequence

Graph Theory 4.1 Graph : In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are

called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. A graph is an ordered pair G: = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V. To avoid ambiguity, this type of graph may be described precisely as undirected and simple.An undirected graph G consists of a set VG of vertices and a set EG of edges such that each edge e 2 EG is associated with an unordered pair of vertices, called its endpoints. A directed graph or digraph G consists of a set VG of vertices and a set EG of edges such that each edge e 2 EG is associated with an ordered pair of vertices. We denote a graph by G = (VG; EG):Two vertices are said to be adjacent if there is an edge connecting the two vertices. Two edges associated to the same vertices are called parallel. An edge incident to a single vertex is called a loop. A loop is an edge (directed or undirected) which starts and ends on the same vertex; these may be permitted or not permitted according to the application. In this context, an edge with two different ends is called a link. A vertex that is not incident on any edge is called an isolated vertex. A graph with neither loops nor parallel edges is called simple graph. If multiple edges are allowed between vertices, the graph is known as a multigraph. Vertices are usually not allowed to be self-connected, but this restriction is sometimes relaxed to allow such "graph loops." A graph that may contain multi edges and graph loops is called a pseudo graph.

Example Consider the following graph G

a. Find EG and VG. b. List the isolated vertices. c. List the loops. d. List the parallel edges. e. List the vertices adjacent to v3:. f. Find all edges incident on v4: Solution. a. EG = fe1; e2; e3; e4; e5; e6g and VG = fv1; v2; v3; v4; v5; v6; v7g: b. There is only one isolated vertex, v5: c. There is only one loop, e5: d. fe2; e3g: e. fv2; v4g: f. fe1; e4; e5g: Example Which one of the following graphs is simple.

Solution. a. is not simple since it has a loop and parallel edges. b. is simple. A complete graph on n vertices, denoted by Kn; is the simple graph that contains exactly one edge between each pair of distinct vertices.

4.2 Multigraph: The term "multigraph" is generally understood to mean that multiple edges (and sometimes loops) are allowed. Some references require that multigraphs possess no graph loops, some

explicitly allow them whereas there are others who uses the term "multigraph" to mean a graph containing either loops or multiple edges. Where graphs are defined so as to allow loops and multiple edges, a multigraph is often defined to mean a graph without loops, however, where graphs are defined so as to disallow loops and multiple edges, the term is often defined to mean a "graph" which can have both multiple edges and loops, although many use the term "pseudograph" for this meaning

4.3 Complete graph: A complete graph is a graph in which each pair of graph vertices is connected by an edge. The complete graph with n graph vertices is denoted Kn and has

(the triangular

numbers) undirected edges, where is a binomial coefficient.The complete graph on n vertices has n vertices and n(n-1)/2 edges, and is denoted by Kn. It is a regular graph of degree n − 1. All complete graphs are their own cliques. They are maximally connected as the only vertex cut (A vertex cut of a connected graph G is a set of vertices whose removal renders G disconnected) which disconnects the graph is the complete set of vertices.In older literature, complete graphs are sometimes called universal graphs. A complete graph with n nodes represents the edges of an (n-1)-simplex. Geometrically K3 relates to a triangle, K4 a tetrahedron, K5 a pentachodron,

etc. 4.4 Bi Graph/Bipartite Graph: A bigraph graph, also called a bipartite, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with k=2. Bi graphs are equivalent to two-colorable graphs, and a graph is bipartite iff all its cycles are of even length

U

V

The two sets U and V may be thought of as a coloring of the graph with two colors: if we color all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a

nonbipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. All trees are bipartite, e.g.

4.5 Degree : The degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted deg (v). The maximum degree of a graph G, denoted by Δ(G), is the maximum degree of its vertices, and the minimum degree of a graph, denoted by δ(G), is the minimum degree of its vertices. 1 3 3

2

1

3 2 0 . In the above graph, the maximum degree is 3 and the minimum degree is 0.

In this graph all of the vertices have degree three.

4.6 Degree Sequence: Given an undirected graph, a degree sequence is a monotonic non increasing sequence of the vertex degrees (valencies) of its graph vertices. The number of degree sequences for a graph of a given order is closely related to graphical partitions. The sum of the elements of a degree sequence of a graph is always even due to fact that each edge connects two vertices and is thus counted twice .For the above graph degree sequence is (3, 3, 3, 2, 2, 1, 0). The minimum vertex degree in a graph G is denoted , and the maximum degree is denoted . A graph whose degree sequence contains only multiple copies of a single integer is called a regular graph.

It is possible for two topologically distinct graphs to have the same degree sequence.