Register

Web Page

Syllabus: Connectivity, Matching, Coloring.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 1&1&0&0&1&1&0&1&0&1&0&0.6&1
\\\hline\textbf{2 Marks Count} & 3 &1&0&1&1&1&0&0&0&0&0&0.7&3
\\\hline\textbf{Total Marks} & 7 &3&0&2&3&3&0&1&0&1&\bf{0}&\bf{2}&\bf{7}\\\hline
\end{array}}}$$

Filter

Recent questions in Graph Theory

0 votes
1 answer
601
find complexity?
What is cyclomatic complexity of below program below: i=0; n=4; while(i<n-1) {j=i+1; while(j<n) {if(A[i]< A[j]) swap (A[i],A[j]);} i=i+1; } A)3 B)4 C)5 D)6
What is cyclomatic complexity of below program below:i=0; n=4;while(i<n-1){j=i+1; while(j<n){if(A[i]< A[j]) swap (A[i],A[j]);}i=i+1;}A)3 B)4 C)5 D)6
User Avatar
0 votes
1 answer
602
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
604
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
2 answers
605
Graph theory
Which is the best book for studying GATE CS Graph theory?
Which is the best book for studying GATE CS Graph theory?
User Avatar
0 votes
1 answer
607
Kenneth Rosen Edition 6th Exercise 8.2 Theorem 1 (Page No. 543)
how to prove that sum of all the vertices in a graph G is equal to twice the number of edges in G. please explain step by step .
how to prove that sum of all the vertices in a graph G is equal to twice the number of edges in G.please explain step by step .
User Avatar
0 votes
1 answer
608
keneth r rosen
how to prove that graph G with e= v - 1 that has no circuit is a tree.
how to prove that graph G with e= v - 1 that has no circuit is a tree.
User Avatar
0 votes
1 answer
609
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
0 votes
2 answers
610
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y What would be maximum path length between any two vertices of graph ?
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhat would be maximum path length bet...
User Avatar
1 votes
1 answer
611
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Which vertex will have highest in degree ?
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhich vertex will have highest in deg...
User Avatar
3 votes
3 answers
612
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Find number of strongly connected components
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yFind number of strongly connected com...
User Avatar
1 votes
1 answer
614
Kenneth Rosen Edition 6th Exercise 8.4 Question 17d (Page No. 575)
The number of paths of length 5 between two different vertices in K4 (complete graph)?
The number of paths of length 5 between two differentvertices in K4 (complete graph)?
User Avatar
0 votes
1 answer
615
Rosen discrete mathematics
a)The number of paths of length 4 between any two adjacent vertices in K3,3 (bipartite graph)? b) The number of paths of length 4 between any two nonadjacent vertices in K3,3 (bipartite graph)?
a)The number of paths of length 4 between any twoadjacent vertices in K3,3 (bipartite graph)?b) The number of paths of length 4 between any twononadjacent vertices in K3,...
User Avatar
0 votes
0 answers
616
Self-Doubt
Every Planar graph have vertex cover of size atmost 3n/4. Can someone provide a good link to understand the above fact? Or a good explanation is most welcome.
Every Planar graph have vertex cover of size atmost 3n/4.Can someone provide a good link to understand the above fact?Or a good explanation is most welcome.
User Avatar
0 votes
1 answer
617
Travelling Salesman problem considering the triangle inequality
Travelling Salesman problem considering the triangle inequality ,tell the procedure of finding the approximate solution in polynomial time using a suitable example.
Travelling Salesman problem considering the triangle inequality ,tell the procedure of finding the approximate solution in polynomial time using a suitable example.
User Avatar
3 votes
3 answers
618
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
15 votes
3 answers
619
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
User Avatar
0 votes
2 answers
620
JNUEE-2016
Consider an undirected graph G with 100 nodes. What is the maximum number of edges to be included in G so that graph is connected? (a) 2451 (b) 4851 (c) 4950 (d) 9990
Consider an undirected graph G with 100 nodes. What is the maximum number of edges to be included in G so that graph is connected?(a) 2451(b) 4851(c) 4950(d) 9990
User Avatar
Page: