Course Outlines

 Basic concepts; Complete graph; Bipartite graphs; Connectivity; Sub graphs; Metric representation of graphs; Isomorphic graphs; Travers ability; Eulerian & Hamiltonian graphs; Properties and applications; Trees; Properties of trees; Spanning tree and minimal spanning trees; Rooted and binary tree; Planar graph; Properties & theorems of planar graphs; Graph coloring; Directed graphs; Diagraph; Connectivity; Traversability; Tournament; Traffic flows.

Introduction

·     Graph: A graph G consists of a nonempty finite set V whose elements are called vertices and a set E of edges such that each edges consists of a pair of distinct vertices. The graph with V vertices and E edges is denoted by G(V, E).

·     Trivial graph: The graph having only one vertex but no edges is called trivial graph.

·     Empty graph: The graph with no vertex and no edges is called empty graph.

·     Loop of a graph: An edge of a graph is called loop if it joints a vertex and itself.

·     Parallel edges: Two or more edges of a graph are called parallel or multiple edges if they have same end points.

·     Finite graph: A graph is said to be finite if both the vertex set and edge set are finite.

·     Adjacent edges: Two edges are said to be adjacent if they have common vertex.

·     Simple graph: A graph is said to be simple if it has no loops no parallel edges.

·     Multigraph: A graph G having multiple edges or having loops is called multigraph.

·     Degree of vertices: The degree of vertex V in graph G is denoted by d(v) is the number of edges which are incident on v. The vertex is said to be even or odd according as d(v) is even or odd.

·     Complete graph: If there exists exactly one edge between any pair of vertices of graph G, then it is said to be complete graph. The complete graph with n vertices is denoted by Kn.

·     Bipartite graph: A graph G is said to be bipartite if its vertices V can be partitioned into two subsets M and N such that each edge of G connects a vertex of M to the vertex of N.

·     Complete bipartite graph: A bipartite graph G is said to be complete bipartite if and only if an edge {x, y} Î E(G) for all x Î M and y Î N.

·     Walk in a graph: A walk in a graph G is a finite order set

                                           W = {v0, e1, u1, e2, u3, ..., uk–1, ek, uk}

          Whose elements are alternately vertices and edges such that for 1 £ i £ k, the edge ei has edge vertices Vi–1 and Vi.

·     Trail and path: A walk in a graph in which all the edges are distinct, is called trail and if all the vertices are distinct, then it is called path.

·     Open and closed walk, trail or path: A walk (trail or path) in graph is said to be closed if the initial vertex u1 and final vertex un such that u1 = un, otherwise it is said to be open.

·     Circuit and cycle: A closed trail which contain at least three edges is called circuit and circuit which does not repeat any vertices except the initial and final vertex is called cycle.

·     Connected and disconnected graph: In a graph G if there is a path between any two of its vertices, then it is said to be connected graph, otherwise it is said to be disconnected.

·     Isomorphism of graphs:  Let G(V1, E1) and H(V2, E2) be two graphs. The graph G and H are said to be isomorphic if there is one to one and onto function f between vertices of G to the vertices of H such that {u, v} is in E, if and only if {f (u), f(v)} is in E2. Such a function f is called an isomorphism.

·     Subgraph: A subgraph of G(V, E) is a graph H(V1, E1) such that (i) V1 Í V and E1 Í E
(ii) for every edge e1 Î E1 is incident on v1 and w1 then v1, w1 Î V1.

·     Induced subgraph: A subgraph H(V1, E1) is vertex induced subgraph of the graph G(V, E) if V1 Í V and E1 = E Ç P2(V1) where P2(V1) a 2-subset of V1 (i.e. if v, u Î V1) and {v, u} Î E iff {u, v} Î E1)

·     Spanning Subgraph: A subgraph H(V1, E1) of graph G(V1 E) is said to be spanning subgraph of G(V, E) if V1 = V.

·     Proper subgraph: A subgraph H (V1, E1) of graph G(V, E) is said to be proper subgraph if either V1 ¹ V or E1 ¹ E.

·     Cut vertex: A vertex v of a connected graph G is called a cut-vertex if the graph G – v is disconnect.

          Bridge: An edge e of a graph G is said to bridge if G – e is disconnected.

·     Matrix representation of a graph: Adjacency matrix: Let G be a graph with n vertices v1, v2, v3 ......., vn. The adjacency matrix of G with respect to a given ordered list of vertices in a n × n matrix, usually denoted by A(G), i.e. A(G) = (aij) where the ijth entry aij is the number of edges joining the vertex vi to vj.

·     Incidence Matrix: Let G be a graph with vertices v1, v2, ....... vp and edges e1, e2, ...... eq. The incidence matrix I(G) of G is a p × q matrix I(G) = (aij) where

          aij = { 1 if ei is incident with vj  o otherwise

·     Eulerian trail and Eulerian Graphs: Let G be a graph. A trail in G is called an Eulerian trial if it contains all the edges of graph G.

          A graph G is called an Eulerian graph if it contains an Eulerian circuit and the circuit intersects each vertex at least once.

·     Traversable graph: A graph G is said to be a traversable graph if G has Eulerian trial.

·     Hamiltonian graph: A graph G is called Hamiltonian graph it has a Hamiltonian circuit.

·     Tree and forest: A connected graph G is called tree if it has no cycle and a forest is a graph whose components are tree.

·     Spanning tree: A subgraph T of a graph G is called a spanning tree of G, if T is tree and all the vertices of graph G is also the vertices of the tree T.

·     Planar graph: A graph is said to be planar if it has a representation in the plane with the edges intersecting only at the vertices on which they are incident.

·     Diagraph: A diagraph D, denoted by D(V, E) consists of a finite non-empty set V of vertices and a finite set E of directed edges of order pair (u, v) of vertices.