Recent questions tagged graph-theory - GATE CSE Doubts

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 2 days ago in Mathematical Logic by Doraemon (89 points) | 9 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 6 days ago in Graph Theory by vishal burnwal (58 points) | 31 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 in Graph Theory by Shivateja MST (68 points) | 20 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 in Graph Theory by Shivateja MST (68 points) | 6 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 in Graph Theory by Shivateja MST (68 points) | 11 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 in Graph Theory by Shivateja MST (68 points) | 18 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 in Graph Theory by Shivateja MST (68 points) | 10 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 in Graph Theory by Shivateja MST (68 points) | 11 views

0 votes

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 in Graph Theory by amit166 (113 points) | 18 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 in Algorithms by pranay562 (666 points) | 58 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 in Graph Theory by Abhipsa Mishra (15 points) | 13 views

0 votes

0 answers

The Gate Academy test
What should be the answer?

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

0 votes

1 answer

doubt on hamiltonian graph statement listed in mathworld.wolfram website

asked Oct 23 in Graph Theory by shaktisingh (87 points) | 36 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 in Mathematical Logic by Prince Sindhiya (9 points) | 47 views

+1 vote

1 answer

GATE GURU: GRAPHS

asked Oct 21 in Graph Theory by Debapaul (310 points) | 28 views

0 votes

0 answers

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

asked Oct 21 in Graph Theory by Debapaul (310 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 in Graph Theory by Debapaul (310 points) | 20 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 in Graph Theory by shaktisingh (87 points) | 20 views

0 votes

1 answer

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

asked Oct 19 in Algorithms by luc_Bloodstone (27 points) | 44 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 in Graph Theory by shaktisingh (87 points) | 11 views

0 votes

0 answers

Kenneth-Rossen
Is grid and hypercube in syllabus?

asked Sep 14 in Mathematical Logic by kshitij (13 points) | 14 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 in Graph Theory by Lakshman Patel RJIT (104 points) | 42 views

0 votes

0 answers

Self Doubt: Discrete Maths

asked Sep 4 in Graph Theory by GAITONDE (1.6k points) | 37 views

0 votes

1 answer

Is hypercube graph is another name of regular graph??

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

0 votes

1 answer

What is maximal independent set(MIS)?

asked Aug 23 in Mathematical Logic by pawarpiyusha1306 (7 points) | 18 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 in Algorithms by iarnav (76 points) | 11 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 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 in Algorithms by Sambhrant Maurya (290 points) | 24 views

0 votes

1 answer

Graph Theory:Self Doubt
What is “arborescence” of a graph?? Need some good example of it.

asked Aug 1 in Graph Theory by srestha (558 points) | 20 views

0 votes

0 answers

GateForum: DS
In the following graph, the number of BFS traversals possible are?

asked Jul 26 in DS by Sambhrant Maurya (290 points) | 25 views

0 votes

1 answer

Kenneth Rosen
6. Consider a graph where its vertices are representing as n bit signal. 2 vertices are only connected with each other if their bit positions only differs by exactly 1 bit (n >= 2). Then the degree sequence of G is ___________________________.

asked Jul 13 in Graph Theory by `JEET (164 points) | 16 views

0 votes

0 answers

Kenneth Rosen-7th edition-Chapter 10/10.8
THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four. Question #40 (10.8) : Show that every planar graph G can be colored using six or fewer colors. Question #41 (10.8) : Show that every planar graph G ... is already stated in the four color theorem that we don't require more than 4 colors in order to color a planar graph.

asked Jul 11 in Graph Theory by Kushagra गुप्ता (155 points) | 11 views

To see more, click for the full list of questions or popular tags.

2,317 questions

1,295 answers

6,601 comments

89,719 users