Download Original PDF
Get the official Barkatullah University print version scanned document.
đ¤ Help Your Juniors!
Have previous year question papers that aren't on our website? Help the next batch of students by sending them to us! With your consent, we will proudly feature your name as a Top Contributor on our platform.
Submit Papers đŠTotal No. of Questions : 11
[Total No. of Printed Pages : 06
OP-502
M.Sc. (REG/PVT./ATKT) Examination, 2024
(Fourth Semester)
MATHEMATICS
Advanced Graph Theory-II
Paper-III
Time : 3 Hours
[Maximum Marks :
Reg. : 85
Pvt. : 100
Note : Attempt all questions.
(Objective Type Questions)
1. Choose the correct answer : 5×3=15
(i) Let G be a connected graph with n vertices, e edges and r regions. Then :
(ii) A connected graph G is an Eulerian graph if all vertices of G are of :
(a) even degree
(b) odd degree
(c) even or odd degree
(d) All of the above
(iii) The minimum number of colors needed to color a graph having n (> 3) vertices and 2 edges is :
(a) 4
(b) 3
(c) 2
(d) 1
(iv) If A(G) is an incidence matrix of a connected graph G with n vertices, then rank of A(G) is :
(a) n
(b) n - 1
(c) n + 1
(d) None of the above
(v) What would be the number of zeroes in the adjacency matrix of the given graph ?
(a) 10
(b) 6
(c) 16
(d) 0
(Short Answer Type Questions) 5×5=25
2. Define incidence matrix with example.
Or
Define fundamental circuit matrix with example.
3. Every cut-set in a connected graph G contains at least one branch of every spanning tree of G. Prove.
Or
Define adjacency matrix with example.
4. Explain Geometrical dual and Combinational dual with an example.
Or
Write a note on chromatic number.
(Long Answer Type Questions) 5×9=45
5. State four color problem.
Or
Explain Digraphs and Binary relations.
6. Define adjacency matrix of a Digraph.
Or
Write a short note on Arboreocence.
7. Explain in detail an application of graph theory in switching network.
Or
Find the incidence matrix and circuit matrix of the digraph (given) :
8. Write various observations that can be made about a path matrix P(x, y) of a graph G.
Or
Draw the graph represented by the following adjacency matrix A :
V1 V2 V3 V4 V5
V1 [0 1 1 0 0]
V2 [1 0 1 0 0]
V3 [1 1 0 1 1]
V4 [0 0 1 0 1]
V5 [0 0 1 1 0]
9. Prove that the chromatic function of a simple graph is a polynomial.
Or
Prove that, if G is a disconnected simple graph, then its chromatic polynomial PG(k) is the product of the chromatic polynomials of its component.
10. Prove that every simple planar graph is 4-colourable.
Or
A graph with maximum degree at most k is (k + 1) colorable.
11. Prove that the maximum number of arc-disjoint paths from a vertex V to a vertex W in a digraph is equal to the minimum number of arcs in a VW-disconnecting set.
Or
Write short notes on the following :
(a) Trees with directed graph
(b) Arboreocence
(c) Matrix of Digraphs.