Register

Recent questions tagged graph-connectivity

2 votes
2 answers
122
Which of the following is the possible sequence of edges when Prim's algorithm is applied ?
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e) (g,f),(f,c),(g,d),(c,e),(d,b),(d,a) (c,f),(c,e),(e,d),(a,b),(d,g),(b,c) None of the above
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e)(g,f),(f,c),(g,d),(c,e),(d,b),(d,a)(c,f),(c,e),(e,d),(a,b),(d,g),(b,c)None of the above
User Avatar
7 votes
1 answer
124
Graph Theory
Graph G(V,E) is a connected planar graph with no cycle of length less than 4 edges, if |V| = 15 then maximum value of |E| is: The answer given is 26.
Graph G(V,E) is a connected planar graph with no cycle of length less than 4 edges, if |V| = 15 then maximum value of |E| is:The answer given is 26.
User Avatar
2 votes
0 answers
125
chromatic number
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
User Avatar
0 votes
1 answer
126
GRAPH THEORY
Let G be an undirected graph on n nodes. Any two of the following statements implies the third. Is it true or False? 1. G is connected. 2. G doesn't have cycles. 3. G contain n-1 edges.
Let G be an undirected graph on n nodes. Any two of the following statements implies the third. Is it true or False?1. G is connected.2. G doesn't have cycles.3. G contai...
User Avatar
0 votes
0 answers
128
DISCRETE
Let G be a connected 3 - regular graph. Each edge of G lies on some cycle. Let S⊆V and C1,C2,…,Cm,m=Codd(G−S), be the odd component of G−S. Let eG(Ci,S) denote the number of edges with one- end in Ci and the other in S. Then eG(Ci,S) is (A) Even (B) Odd (C) Cannot say
Let G be a connected 3 - regular graph. Each edge of G lies on some cycle. Let S⊆V and C1,C2,…,Cm,m=Codd(G−S), be the odd component of G−S. Let eG(Ci,S) denote t...
User Avatar
0 votes
0 answers
129
discrete mathematics
Let T be an n - vertex tree having one vertex of degree i for i=2,3,…,k and the remaining n−k+1 vertices are of degree 1 each. Determine n in terms of k.
Let T be an n - vertex tree having one vertex of degree i for i=2,3,…,k and the remaining n−k+1 vertices are of degree 1 each. Determine n in terms of k.
User Avatar
1 votes
1 answer
132
Graph theory Narshing Deo
theorem no 10.1 Narsingh Deo prove that the no. of labeled graph of n vertices of n is 2^(n(n-1)/2)
theorem no 10.1 Narsingh Deoprove that the no. of labeled graph of n vertices of n is 2^(n(n-1)/2)
User Avatar
1 votes
2 answers
133
graph theory
can we say a null graph is eulerian circuit and hamiltonian circuit?
can we say a null graph is eulerian circuit and hamiltonian circuit?
User Avatar
3 votes
3 answers
134
[Discrete Maths] Graph Theory Rosen,Chromatic number
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?
What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?
User Avatar
2 votes
2 answers
135
Discrete Maths Graph theory
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
User Avatar
3 votes
1 answer
136
[Discrete Maths] Graph theory
What is the vertex connectivity and edge connectivity of complete graph? Is it n or n-1?
What is the vertex connectivity and edge connectivity of complete graph?Is it n or n-1?
User Avatar
2 votes
1 answer
140
2 - connected graph
For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$ ... 3 regular and not 2- connected although $d \geq 2$ is satisfied. Why this $d \geq 2$ is trivial and not working in some cases ?
For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$ - connected. (vertex wise).I did in this way :$\begin{alig...
User Avatar
0 votes
1 answer
143
nptel exam ada
Total no of edges =1225 Maximum degree of vertex =3 find no of vertices ?
Total no of edges =1225Maximum degree of vertex =3find no of vertices ?
User Avatar
0 votes
0 answers
145
Graph Theory
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
User Avatar
0 votes
1 answer
146
Relation between k and k-1 edge connected graph
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
User Avatar
3 votes
3 answers
148
graph theory
A graph consists of only one vertex,which is isolated ..Is that graph A) a complete graph ??? B) a clique??? C) connected graph ??? Please explain your answer ...
A graph consists of only one vertex,which is isolated ..Is that graphA) a complete graph ???B) a clique???C) connected graph ???Please explain your answer ...
User Avatar
1 votes
4 answers
150
graph theory
chromatic number of a graph <= ( maxdegree of the graph ) + 1 can somebody explain how ?
chromatic number of a graph <= ( maxdegree of the graph ) + 1 can somebody explain how ?
User Avatar
Page: