Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

1 votes
1 answer
723
UGC NET CSE | December 2012 | Part 2 | Question: 33
Consider the tree given below: Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree: d & h c & k g, b, c, h, i, m c & h
Consider the tree given below:Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree:d & hc & kg, b, c, h, i, mc & h
User Avatar
1 votes
2 answers
724
Find given graph is planar, Hamiltonian or eulerian
The graph in the figure is a portion of the Shri Chakra. Is it : (1) a Planar graph ? (2) a Hamiltonian graph ? (3) an Eulerian graph ? (A) 1 and 2 (B) 2 and 3 (C) 1 and 3 (D) 1, 2 and 3
The graph in the figure is a portion of the Shri Chakra.Is it :(1) a Planar graph ?(2) a Hamiltonian graph ?(3) an Eulerian graph ?(A) 1 and 2(B) 2 and 3(C) 1 and 3(D) 1,...
User Avatar
4 votes
3 answers
725
UGC NET CSE | June 2012 | Part 3 | Question: 72
$G_1$ and $G_2$ are two graphs as shown: Both $G_1$ and $G_2$ are planar graphs Both $G_1$ and $G_2$ are not planar graphs $G_1$ is planar and $G_2$ is not planar $G_1$ is not planar and $G_2$ is planar
$G_1$ and $G_2$ are two graphs as shown:Both $G_1$ and $G_2$ are planar graphsBoth $G_1$ and $G_2$ are not planar graphs$G_1$ is planar and $G_2$ is not planar$G_1$ is no...
User Avatar
0 votes
1 answer
726
chromatic number
User Avatar
3 votes
2 answers
727
UGC NET CSE | June 2012 | Part 3 | Question: 31
The upper bound of computing time of m colouring decision problem is $O(nm)$ $O(n^m)$ $O(nm^n)$ $O(n^mm^n)$
The upper bound of computing time of m colouring decision problem is$O(nm)$$O(n^m)$$O(nm^n)$$O(n^mm^n)$
User Avatar
11 votes
4 answers
728
ISRO2016-5
A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are of same degree even degree odd degree different degree
A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are ofsame degree even degreeodd degree ...
User Avatar
1 votes
2 answers
729
UGC NET CSE | June 2012 | Part 2 | Question: 4
The number of colours required to properly colour the vertices of every planer graph is 2 3 4 5
The number of colours required to properly colour the vertices of every planer graph is2345
User Avatar
1 votes
2 answers
730
UGC NET CSE | June 2014 | Part 2 | Question: 23
Consider a complete bipartite graph $k_{m,n}$. For which values of $m$ and $n$ does this, complete graph have a Hamilton circuit $m = 3, n = 2$ $m = 2, n = 3$ $m = n > 2$ $m = n > 3$
Consider a complete bipartite graph $k_{m,n}$. For which values of $m$ and $n$ does this, complete graph have a Hamilton circuit $m = 3, n = 2$$m = 2, n = 3$ $m = n 2$$m...
User Avatar
2 votes
2 answers
731
UGC NET CSE | June 2014 | Part 2 | Question: 21
Consider the graph given below as : Which one of the following graph is isomorphic to the above graph ?
Consider the graph given below as :Which one of the following graph is isomorphic to the above graph ?
User Avatar
0 votes
2 answers
732
Check whether graph with following degrees are possible?
Check whether graph with following degrees are possible? I) 6, 6, 6, 6, 3, 3, 2, 2 II) 7, 6, 6, 4, 4, 3, 2, 2 (How to solve this type of questions? Please explain..)
Check whether graph with following degrees are possible?I) 6, 6, 6, 6, 3, 3, 2, 2II) 7, 6, 6, 4, 4, 3, 2, 2(How to solve this type of questions? Please explain..)
User Avatar
4 votes
2 answers
733
All pair shortest path
Algorithm which solves the all pair shortest path problem is A)Dijkstra's algorithm B)Floyd's algorith C)Prim's algorithmm D)Warshall's algorithm
Algorithm which solves the all pair shortest path problem isA)Dijkstra's algorithmB)Floyd's algorithC)Prim's algorithmmD)Warshall's algorithm
User Avatar
0 votes
1 answer
734
Data Structure Graph
What is the minimum number of edges which must be removed from a complete bipartite graph of six nodes K(6) so that the remaining graph is a planar? Explain with exp why your answer is Right .
What is the minimum number of edges which must be removed from a complete bipartite graph of six nodes K(6) so that the remaining graph is a planar?Explain with exp why y...
User Avatar
8 votes
3 answers
735
ISRO2009-56
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most $n$ edges $n-k$ edges $(n-k) (n-k+1)$ edges $(n-k) (n-k+1)/2$ edges
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...
User Avatar
7 votes
3 answers
736
ISRO2009-55
In a graph $\text{G}$ there is one and only one path between every pair of vertices then $\text{G}$ is a Path Walk Tree Circuit
In a graph $\text{G}$ there is one and only one path between every pair of vertices then $\text{G}$ is aPathWalkTreeCircuit
User Avatar
9 votes
1 answer
737
ISRO2009-54
A graph in which all nodes are of equal degree, is known as Multigraph Non regular graph Regular graph Complete graph
A graph in which all nodes are of equal degree, is known asMultigraphNon regular graphRegular graphComplete graph
User Avatar
8 votes
1 answer
738
ISRO2009-52
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is $e$ $e/2$ $e^2$ $2 e$
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is$e$$e/2$$e^2$$2 e$
User Avatar
8 votes
1 answer
740
ISRO2008-78
Consider the graph shown in the figure below: Which of the following is a valid strong component? $a, c, d$ $a, b, d$ $b, c, d$ $a, b, c$
Consider the graph shown in the figure below:Which of the following is a valid strong component?$a, c, d$$a, b, d$$b, c, d$$a, b, c$
User Avatar
3 votes
3 answers
741
UGC NET CSE | June 2013 | Part 2 | Question: 37
Which of the following connected graph has exactly one spanning tree? Complete graph Hamiltonian graph Euler graph None of the above
Which of the following connected graph has exactly one spanning tree? Complete graph Hamiltonian graph Euler graph None of the above
User Avatar
1 votes
1 answer
742
Graph having every pair of vertices connected is called
Graph having every pair of vertices connected is called Cycle graph Complete graph Peterson graph Is a Tree
Graph having every pair of vertices connected is calledCycle graphComplete graphPeterson graphIs a Tree
User Avatar
1 votes
2 answers
743
An undirected graph G has n vertices and n-1 edges then G is
An undirected graph G has n vertices and n-1 edges then G is A. Cyclic B. Addition of edge will make it cyclic C. Eulerian D. Is a Tree
An undirected graph G has n vertices and n-1 edges then G isA. CyclicB. Addition of edge will make it cyclicC. EulerianD. Is a Tree
User Avatar
2 votes
2 answers
744
An undirected graph is Eulerian if and only if all vertices of G are of the sum of the degrees of all nodes is
An undirected graph is Eulerian if and only if all vertices of G are of the sum of the degrees of all nodes isA. Same degreeB. ODD degreeC. Need not be ODDD. ...
User Avatar
7 votes
2 answers
745
ISRO2007-62
Let $X$ be the adjacency matrix of a graph $G$ with no self loops. The entries along the principal diagonal of $X$ are all zeros all ones both zeros and ones different
Let $X$ be the adjacency matrix of a graph $G$ with no self loops. The entries along the principal diagonal of $X$ areall zerosall onesboth zeros and onesdifferent
User Avatar
8 votes
2 answers
746
ISRO2007-07
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is $1$ $k$ $k-1$ $k/2$
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is$1$$k$$k-1$$k/2$
User Avatar
11 votes
2 answers
747
ISRO2007-06
A graph with $n$ vertices and $n-1$ edges that is not a tree, is Connected Disconnected Euler A circuit
A graph with $n$ vertices and $n-1$ edges that is not a tree, isConnectedDisconnectedEulerA circuit
User Avatar
Page: