Q. 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?

View solution

Q. A bridge can not be a part of _______

View solution

Q. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______

View solution

Q. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______

View solution

Q. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.

View solution

Q. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?

View solution

Q. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.

View solution

Q. The minimum number of edges in a connected cyclic graph on n vertices is _____________

View solution

Q. The maximum number of edges in a 8-node undirected graph without self loops is ____________

View solution

Q. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____

View solution

Q. The 2ⁿ vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G can be ___________

View solution

Q. A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).

View solution

Q. Every Isomorphic graph must have ________ representation.

View solution

Q. A cycle on n vertices is isomorphic to its complement. What is the value of n?

View solution

Q. How many perfect matchings are there in a complete graph of 10 vertices?

View solution

Q. A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)

View solution

Q. A complete n-node graph Kn is planar if and only if _____________

View solution

Q. A graph is ______ if and only if it does not contain a subgraph homeomorphic to k₅ or k₃,₃.

View solution

Q. An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if ____________

View solution

Q. What is the grade of a planar graph consisting of 8 vertices and 15 edges?

View solution