Recent questions tagged graph-theory - GATE CSE Doubts

0 votes

1 answer

Self doubtful : Discrete Maths
Every Kn,n is Hamilton graph. True or False?

asked 9 hours ago in Graph Theory by Chirag Shilwant (159 points) | 9 views

0 votes

1 answer

Self doubt graph theory Hamilton graph
graph G which has a cut edge cannot be Hamiltonian ?

asked 2 days ago in Graph Theory by Ram Swaroop (155 points) | 42 views

0 votes

0 answers

Applied course test series- DS
Which of the following statements is/are true? Converting an adjacency matrix representation to an adjacency list representation takes O(V+E) time. In any connected undirected graph with exactly 5 simple cycles (that do not share any edges), there are at most 10 ... between every pair of vertices Options: Only I Only II Both I and II Neither I nor II PS.: Answer is d.

asked 2 days ago in DS by Shubhranshu Maurya (8 points) | 14 views

0 votes

1 answer

The maximum value of the minimum degree in connected planar bipartite graph is ____?

asked 3 days ago in Mathematical Logic by smosh (6 points) | 31 views

+2 votes

0 answers

MADE EASY TEST: BIPARTITE GRAPH
Maximum value of the minimum degree in a connected planar bipartite graph is ?

asked Jan 12 in Graph Theory by Debapaul (620 points) | 56 views

0 votes

1 answer

MADE EASY FLT: GRAPH THEORY
What is the $cardinality$ of the $largest$ $independent$ $set$ of this graph?

asked Jan 10 in Graph Theory by Debapaul (620 points) | 28 views

+1 vote

1 answer

Made Easy test series multiple subject graph theory

asked Jan 8 in Mathematical Logic by Ram Swaroop (155 points) | 35 views

0 votes

0 answers

Madeeasy test series - find order of relaxed vertices in a graph using dijkstra algo

asked Jan 8 in Algorithms by luc_Bloodstone (33 points) | 18 views

0 votes

1 answer

doubt on statement of a simple graph
i was reading about simple graph there a statement is written The mean number of edges for graphs with vertices is given by , giving the sequence for , 2, ... of 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, .. explain this statement with an example? what is this mean number of edges?

asked Jan 5 in Graph Theory by shaktisingh (90 points) | 24 views

0 votes

0 answers

Isomorphism self doubt
Whether 2 finite graph are isomorphic or not is a __________ problem (Assume P ! =NP) 1. NP Hard but not Np-Complete 2. Np-Complete 3. NP but not Np-Complete 4. None of the above

asked Dec 28, 2019 in Graph Theory by Chirag Shilwant (159 points) | 11 views

0 votes

0 answers

Applied GATE grand test 4 - Graph theory
State true or False with explanation.

asked Dec 26, 2019 in Graph Theory by Satbir (4.1k points) | 51 views

0 votes

1 answer

Graph theory
Which of the following graphs are not bipartite? (a) I,II (b) I,II,III c) I,III d) II,III

asked Dec 25, 2019 in Graph Theory by haralk10 (54 points) | 40 views

0 votes

0 answers

GRAPH THEORY-self doubt
In GATE If suppose nothing is mentioned about the type of vertices then do we consider them to be labelled/unlabelled by default?

asked Dec 10, 2019 in Mathematical Logic by Doraemon (91 points) | 10 views

0 votes

0 answers

Self Doubt : Graph Theory
How to know that a simple graph with given degree sequence {3,3,3,3,3,3,6} is hamiltonian or not.

asked Dec 6, 2019 in Graph Theory by vishal burnwal (119 points) | 33 views

0 votes

1 answer

Graph thoery MCQ
Which of the following statements are true? If a simple graph G is not connected,then its complement G' is connected. If a simple graph G is connected,then its complement G' is not connected. A simple graph G with n vertices is necessarily ... simple graph has exactly two vertices of odd degree then there exists a path between two vertices of odd degree. Anyone please clarify.

asked Dec 2, 2019 in Graph Theory by Shivateja MST (96 points) | 21 views

0 votes

0 answers

Graph Theory Complement of Graph
If a Graph G have n vertices and all but one of odd degree,then no. of vertices of odd degree in G’ is ____ Assume G is a simple connected graph. Anyone please clarify.

asked Dec 2, 2019 in Graph Theory by Shivateja MST (96 points) | 9 views

0 votes

0 answers

Independent Set Vs Matching
Is the problem of Independent Set same as problem of finding Maximum matching of a Graph? Anyone please clarify with some example.

asked Nov 30, 2019 in Graph Theory by Shivateja MST (96 points) | 13 views

0 votes

0 answers

Mathematics Graph Theory doubt
It is given “A complete bipartite graph Km,n is planar iff m<=2 or n<=2” But it has to be m<=2 and n<=2 right? Anyone please clarify.

asked Nov 29, 2019 in Graph Theory by Shivateja MST (96 points) | 21 views

0 votes

0 answers

Hamiltonian cycles Graph Theory
Can anyone explain how to identify distinct Hamiltonian edge cycles in a graph with some example? Here distinct implies w.r.t structure or w.r.t order? Suppose if we consider K3, if we consider any order like 1-2-3-1 or 1-3-2-1 or 2-3-1-2 or ... 3-1-2-3 or 3-2-1-3. All these have same structures and some are obtained by reversing some of the orders. Please clarify.

asked Nov 29, 2019 in Graph Theory by Shivateja MST (96 points) | 11 views

0 votes

1 answer

Mathematics Graph theory
How many simple graphs are possible with n vertices and m edges (m < C(n,2))? Anyone please clarify.

asked Nov 28, 2019 in Graph Theory by Shivateja MST (96 points) | 13 views

+1 vote

0 answers

# graph theory
Q.consider an undirected graph of eight vertices.The probability that there is an edge between a pair of vertices is 1/2 .what is the expected number of unordered cycle of length altest three

asked Nov 28, 2019 in Graph Theory by amit166 (138 points) | 21 views

0 votes

1 answer

Self doubt on Graph theory Question
Let Graph $G$ has 1 vertex of degree $3$, 3 vertices of degree $2$ and 1 vertex of degree $1$. Is $G'$connected or Disconnected ?

asked Nov 25, 2019 in Algorithms by pranay562 (918 points) | 59 views

0 votes

0 answers

Self Doubt in Graph Theory - Subgraph topic
What is the difference between vertex induced subgraph and edge induced subgraph? Which one is the default case to be considered? Thanks!

asked Nov 25, 2019 in Graph Theory by Abhipsa Mishra (15 points) | 15 views

0 votes

0 answers

The Gate Academy test
What should be the answer?

asked Nov 21, 2019 in Graph Theory by Abhipsa Mishra (15 points) | 16 views

0 votes

1 answer

doubt on hamiltonian graph statement listed in mathworld.wolfram website

asked Oct 23, 2019 in Graph Theory by shaktisingh (90 points) | 37 views

+1 vote

1 answer

Self doubt -non isomorphic graph
Consider a graph G and it's complement is denoted by G', how many non isomorphic graph G exist such that G and G' both are bipartite??

asked Oct 22, 2019 in Mathematical Logic by Prince Sindhiya (9 points) | 48 views

+1 vote

1 answer

GATE GURU: GRAPHS

asked Oct 21, 2019 in Graph Theory by Debapaul (620 points) | 29 views

0 votes

0 answers

Self Doubt: Discrete Maths 101
Does Euler graph must contain Euler path? Is the converse true?

asked Oct 21, 2019 in Graph Theory by Debapaul (620 points) | 17 views

0 votes

1 answer

MADE EASY DISCRETE MATHS
Number of perfect matching in a complete graph of 5 vertices is _____ ANS should be 0 right? as when odd number of vertices are there we should have no matching right? But they have applied the matching formula and solved it. God knows why

asked Oct 21, 2019 in Graph Theory by Debapaul (620 points) | 21 views

0 votes

0 answers

self-Doubt in edge formula for line graph
The line graph of a graph with nodes, edges, and vertex degrees contains nodes and edges (ref. Skiena 1990, p. 137) Question : does the no of edges in line graph(given below) got through e' formula is right? I am getting no of edges in ... 3 edges but it is 8 edges as we can see in the below line graph Please validate the edge formula of the line graph.

asked Oct 20, 2019 in Graph Theory by shaktisingh (90 points) | 20 views

0 votes

1 answer

Find number of Minimum cost spanning tree possible? (MadeEasy Test Series)

asked Oct 19, 2019 in Algorithms by luc_Bloodstone (33 points) | 46 views

0 votes

0 answers

self doubt in no of regions in this graph
how to find regions in this graph manually?

asked Oct 12, 2019 in Graph Theory by shaktisingh (90 points) | 11 views

0 votes

0 answers

Kenneth-Rossen
Is grid and hypercube in syllabus?

asked Sep 14, 2019 in Mathematical Logic by kshitij (13 points) | 15 views

0 votes

0 answers

Hamiltonian path
How many Hamiltonian paths are there on the graph above(the graph is labelled)? 1 5 10 120

asked Sep 10, 2019 in Graph Theory by Lakshman Patel RJIT (111 points) | 42 views

0 votes

0 answers

Self Doubt: Discrete Maths

asked Sep 4, 2019 in Graph Theory by GAITONDE (1.7k points) | 37 views

0 votes

1 answer

Is hypercube graph is another name of regular graph??

asked Aug 23, 2019 in Mathematical Logic by pawarpiyusha1306 (7 points) | 32 views

0 votes

1 answer

What is maximal independent set(MIS)?

asked Aug 23, 2019 in Mathematical Logic by pawarpiyusha1306 (7 points) | 20 views

0 votes

0 answers

#Algorithms #Graphs Minimum Number of edges.
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from vertex i to a vertex j iff either j = i+1 or j = 4i. The minimum number of edges in a path in G from vertex 1 to 100 is ? I am getting 6 ... as answer but correct answer is 9 edges. The pattern of edges I'm following - 1 → 4 → 5 → 6 -→ 24 → 25 → 100

asked Aug 19, 2019 in Algorithms by iarnav (76 points) | 12 views

0 votes

0 answers

Kenneth Rosen Edition 7 Exercise 10.2 Question 44
Suppose that $d_{1}, d_{2}, ..., d_{n}$ is a graphic sequence. Show that there is a simple graph with vertices $v_{1}, v_{2}, …, v_{n}$ such that deg($v_{i}$) = $d_{i}$ for i = 1,2, …, n and $v_{1}$ is adjacent to $v_{2}, …, v_{d1 + 1}$.

asked Aug 11, 2019 in Graph Theory by dhruv_sachdev (10 points) | 12 views

0 votes

1 answer

Self Doubt in Algorithms
State true or false, with explanation for a graph G and a constant c>0: Adding c to every edge of G can change the graph's Minimal Spanning Tree. Subtracting c from every edge of G can change the graph's Minimal Spanning Tree. ... can change the shortest path between two vertices. Multiplying c to every edge of G can change the shortest path between two vertices.

asked Aug 4, 2019 in Algorithms by Sambhrant Maurya (341 points) | 24 views

Page:

3,036 questions

1,524 answers

9,070 comments

89,821 users