Recent questions tagged graph-theory

1 votes
0 answers
482
Hi Guys,There is no algorithm to find graph isomorphism (as mentioned by @Rupendra Choudhary) then how much time does Brute force algorithm will takes (means one answer c...
0 votes
1 answer
483
1. whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex.2. if a cut vertex exists, then a cut edge may or may not ...
0 votes
0 answers
489
The bipartite graph G = (V ,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsetsA of V1.
2 votes
1 answer
490
0 votes
0 answers
491
Check which of the following can be chromatic polynomials of a non-null graph ?i) x5 - 4x3 - 2x2 + x + 4ii) x6 - 3x5 + 2x4 - 1P.S I know for a non-null graph G, X(G) (i.e...
1 votes
0 answers
492
What type of graph is STAR?A. BipartiteB. TripartiteC. MutipartitePS : I know a star graph is bipartite but can't we say that a bipartite graph is also tripartite . I. E...
3 votes
0 answers
493
While going through dijkstra's algorithm, there is a term "decrease key". I am not getting the meaning when it says "we do decrease key operation". What exactly we do and...
4 votes
1 answer
494
How many undirected graphs are possible with n verticesif graphs are not necessarily connectedif they are necessarily connected
0 votes
1 answer
496
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...
1 votes
0 answers
500
https://gateoverflow.in/2604/gate1995_1-17 .What is the degree of a node in a tree? Is it same as a graph OR the number of children of that node?
0 votes
0 answers
501
"A planar graph need not to be connected" Can someone plz explain with an example .
0 votes
0 answers
502
0 votes
1 answer
503
0 votes
1 answer
504
1 votes
2 answers
506
The total number of non isomorphic graph which can be formed with 3 vertices________________________
1 votes
1 answer
509
0 votes
1 answer
510
Can anyone explain "closure of relation" or share link for that.