Department of Engineering and Technological
Studies, University of Kalyani
B.Tech. Pt-III (IT) 1st Semester
Examination, 2023
Subject: Graph Theory (Elective I)
Paper: IT506B
Full marks=70 Time: 3 Hours
The figures in the right-hand margin indicate
marks.
Candidate are required to give their answers
in their own words as far as possible.
The notations follow their
standard meanings.
Answer question number one and any
five from rest.
1. Answer any ten questions: (2 x 10 = 20)
a) Define a graph and a subgraph.
b) What are the edge and vertex labeling?
c) Define order and size of a graph.
d) What do you mean by cut edge and
cut vertex?
e) Explain union and intersection of two graphs.
f) A non-directed graph G has 8 edges.
Find the number of vertices,
if the degree of each vertex in G is 2.
g) What is cycle graph,
differentiate it from wheel graph?
h)What is meant by complement of a graph?
Find the complement of the cycle (C5) graph?
i) What is a complete graph?
Find the degree of each vertex in a
complete(K5) graph?
j) If G is a simple connected graph with
70 vertices,
then the number of edges of G is
between ---------
and --------- . Explain.
k) Suppose that G is a graph such that
each vertex has degree 4 and
|E|=4*|V| - 36. Then |V| = ---------
and |E| = --------- .
l) What is rooted tree?
Define level of a vertex in a rooted tree.
m) Determine the order and size of
k-partite complete Kn1,n2,...nk graph.
n) Define simple path and circuit in a graph.
o) Define loop-graph and multi-graph.
2. a) Prove that, in any non-directed graph
there is an even number of vertices of odd
degree.
b) How many different simple graphs are
there with the give verticex set
{v1, v2,...., vn}?
c) Suppose that G is a non directed graph
with 12 edges. Suppose that G has
6 vertices of degree 3 and the rest
have degrees less than 3.
Determine the minimum number of vertices
G can have.
(2+4+4)
3. a) Is there a graph with degree sequence
(1, 3, 3, 3, 5, 6, 6) ?
b) Draw a nonsimple graph ‘G’ with degree
sequence (1, 1, 3, 3, 3, 4, 6, 7) .
c) For any simple graph G,
prove that the number of edges of G is less
than or equal to n(n-1)/2, where n is the
number of vertices of G.
( 2+3+5)
4. a) Define isomorphism.
Determine whether the following
pair of graphs ‘H’ and ‘I’ are isomorphic.
b) Determine the graph G with adjacency
matrix A such that
and (5+5)
5. a) If G is a connected planar graph,
then prove that the Euler’s formula
(|V|-|E|+|R| = 2).
b) In a connected simple-plane graph G,
with |E| > 1, prove that |E| ≤ 3|V| - 6.
c) A complete graph Kn is planar iff n ≤ 4,
justify.
(4+4+2)
6. a) What do you mean by planar graphs?
b) Define dual graph and self-dual graph?
c) Show that the graph ‘I’ given below is
planar.
Find the dual graph of a planar graph ‘J’.
Is it self-dual graph?
7. a) Differentiate between Euler path and
Hamiltonian path.
b) Define chromatic number X(G).
Find the X(G) of a graph ‘M’.
c) What do you mean by a bipartite graph?
d) Find number of all possible binary tree of
3-node.
(2+3+2+3)
8. Short notes:
(2 x 5)
Answer any two of the following:
a) The four-color Problem.
b) The Hamiltonian Graphs.
c) The Königsberg Bridges Problem.
d) The Catalan numbers.
--------End---------------------
.png)
No comments:
Post a Comment