1. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be ______
a) 728
b) 450
c) 360
d) 260
2. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of __________
a) 24
b) 23
c) 176
d) 54
.
3. Triangle free graphs have the property of clique number is __________
a) less than 2
b) equal to 2
c) greater than 3
d) more than 10
4. Berge graph is similar to ______ due to strong perfect graph theorem.
a) line graph
b) perfect graph
c) bar graph
d) triangle free graph
5. Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
a) 4
b) 0
c) 2
d) 5
6. A ______ is a graph which has the same number of edges as its complement must have number of vertices congruent to 4m or 4m modulo 4(for integral values of number of edges).
a) Subgraph
b) Hamiltonian graph
c) Euler graph
d) Self complementary graph
7. In a ______ the vertex set and the edge set are finite sets.
a) finite graph
b) bipartite graph
c) infinite graph
d) connected graph
.
8. If G is the forest with 54 vertices and 17 connected components, G has _______ total number of edges.
a) 38
b) 37
c) 17/54
d) 17/53
9. The number of edges in a regular graph of degree 46 and 8 vertices is ____________
a) 347
b) 230
c) 184
d) 186
Explanation: In a complete graph which is (n-1) regular (where n is the number of vertices) has edges n*(n-1)/2. In the graph n vertices are adjacent to n-1 vertices and an edge contributes two degree so dividing by 2. Hence, in a d regular graph number of edges will be n*d/2 = 46*8/2 = 184.10. An undirected graph G has bit strings of length 100 in its vertices and there is an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position. Determine the ratio of the chromatic number of G to the diameter of G?
a) 1/2101
b) 1/50
c) 1/100
d) 1/20
