Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

1 votes
2 answers
362
Graph Theory #self doubt
Can both euler path and euler circuit exist in same graph. Can both Hamiltonian path and Hamiltonian circuit exist in same graph.
Can both euler path and euler circuit exist in same graph.Can both Hamiltonian path and Hamiltonian circuit exist in same graph.
User Avatar
0 votes
1 answer
363
Clique with one vertex
Is there a clique possible in Graph with one vertex? I mean, is a singleton vertex in itself is a complete sub-graph and can be called a clique.
Is there a clique possible in Graph with one vertex? I mean, is a singleton vertex in itself is a complete sub-graph and can be called a clique.
User Avatar
0 votes
1 answer
365
Graph Theory & Permutations
Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph? Also, if possible generalise the method for graph with k connected components each having ni vertices. Ans=84
Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph?Also, if possible generalise the method for graph with ...
User Avatar
1 votes
2 answers
366
IISc CDS (MTech-R)
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?
User Avatar
0 votes
1 answer
368
Spanning trees
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
User Avatar
0 votes
1 answer
369
Self Doubt
How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?
How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?
User Avatar
0 votes
1 answer
370
Induction
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2 \end{align*}
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2\end{align*}
User Avatar
0 votes
1 answer
371
Regular polyhedra
Is regular polyhedra in graph theory in our Gate syllabus 2019?
Is regular polyhedra in graph theory in our Gate syllabus 2019?
User Avatar
1 votes
1 answer
372
Self doubt
Is this statement correct?? and why? .If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail.
Is this statement correct?? and why?.If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dij...
User Avatar
7 votes
3 answers
373
ISRO2018-38
The number of edges in a regular graph of degree: $d$ and $n$ vertices is: maximum of $n$ and $d$ $n +d$ $nd$ $nd/2$
The number of edges in a regular graph of degree: $d$ and $n$ vertices is:maximum of $n$ and $d$ $n +d$$nd$$nd/2$
User Avatar
1 votes
1 answer
374
PGEE 2018
Consider Undirected Graph G having vertex V {A,B,C,D,E} and edge pair as E {AB BD BE AC CE CD} A) Given graph is disconnected B) Given graph is complete C) Given graph has vertex connectivity 2 D) Given graph has edge connectivity 1
Consider Undirected Graph Ghaving vertex V {A,B,C,D,E}and edge pair as E {AB BD BE AC CE CD}A) Given graph is disconnectedB) Given graph is completeC) Given graph has ver...
User Avatar
1 votes
1 answer
377
Narsingh Deo Problem 2-28
User Avatar
1 votes
1 answer
379
Graph Theory
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
User Avatar
0 votes
0 answers
380
Number of Possible Trees
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
User Avatar
0 votes
1 answer
381
#Graph Theory Any Simple way to prove this ?
A connected graph ‘G’ may have at most (n–2) cut vertices.
A connected graph ‘G’ may have at most (n–2) cut vertices.
User Avatar
1 votes
1 answer
382
Graph Book
The maximum number of edges in a n-node undirected graph WITH self-loops is?
The maximum number of edges in a n-node undirected graph WITH self-loops is?
User Avatar
2 votes
0 answers
385
Algorithm :- Detect Cycle in a graph
Write $O(n)$ time algorithm to find any cycles in a graph. Print NONE otherwise
Write $O(n)$ time algorithm to find any cycles in a graph. Print NONE otherwise
User Avatar
1 votes
2 answers
386
Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithms-time-complexity
Can someone solve this?Also please attempt this question on Algorithms time complexity if interested :)https://gateoverflow.in/210836/algorithms-time-complexity
User Avatar
1 votes
1 answer
390
Graph theory
As a triangle graph is $2 -$ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can someone tell me where did I go wrong? Thanks
As a triangle graph is $2 -$ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can ...
User Avatar
Page: