Recent questions tagged graph-theory

0 votes

1 answer

1

Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________

asked 19 hours ago in Graph Theory by srestha Veteran (114k points) | 27 views

+2 votes

0 answers

2

IISc CSA - Research Interview Question
Prove that the rank of the Adjacency Matrix which is associated with a $k-$ regular graph is $k.$

asked 1 day ago in Graph Theory by ankitgupta.1729 Boss (11.4k points) | 43 views

+1 vote

1 answer

3

GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8

asked 4 days ago in Graph Theory by Hirak Active (2.1k points) | 53 views

0 votes

1 answer

4

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

asked May 12 in Graph Theory by chandan2teja (23 points) | 37 views

0 votes

1 answer

5

IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these

asked Apr 29 in DS by manikgupta123 (115 points) | 89 views

0 votes

0 answers

6

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

asked Apr 28 in Graph Theory by gmrishikumar Active (1.8k points) | 38 views

0 votes

0 answers

7

ISI2017-PCB-B-1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.

asked Apr 8 in Graph Theory by akash.dinkar12 Boss (40.6k points) | 27 views

0 votes

0 answers

8

Graph Decomposition
What is Graph Decomposition & is it in the syllabus? If it is then please can anyone share some online resources for it. Thank you.

asked Mar 17 in Graph Theory by noxevolution (103 points) | 26 views

0 votes

0 answers

9

Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph

asked Mar 5 in Graph Theory by Winner (269 points) | 48 views

0 votes

0 answers

10

JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3

asked Feb 18 in Graph Theory by Sayan Bose Loyal (6.9k points) | 69 views

+1 vote

7 answers

11

GATE2019-12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$

asked Feb 7 in Graph Theory by Arjun Veteran (400k points) | 2.7k views

+1 vote

1 answer

12

GATE2019-38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

asked Feb 7 in Graph Theory by Arjun Veteran (400k points) | 2.3k views

0 votes

1 answer

13

GATE 2019 8
Q.8 Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to 1. (n-1)!/2 2. 1 3.(n-1)! 4. n!

asked Feb 7 in Graph Theory by Ram Swaroop Active (2.6k points) | 324 views

0 votes

0 answers

14

GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?

asked Jan 30 in Graph Theory by Ashish Goyal (423 points) | 112 views

0 votes

1 answer

15

#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.

asked Jan 29 in Graph Theory by amit166 Junior (761 points) | 70 views

0 votes

0 answers

16

Counting

asked Jan 25 in Graph Theory by screddy1313 (477 points) | 36 views

0 votes

0 answers

17

Number of sub graphs possible
Number of labelled subgraphs possible for the graph given below______________

asked Jan 25 in DS by Nandkishor3939 Active (1.2k points) | 83 views

0 votes

1 answer

18

Virtual Gate
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?

asked Jan 24 in Graph Theory by sudharshan (289 points) | 71 views

0 votes

0 answers

19

Homomorphic and Isomorphic graph
This a random question came into my mind… Are the below statements true: 1] If a graph is Homomorphic to our graph then it is also Isomorphic to that graph. 2]If a graph is Isomorphic to our graph then it is also Homomorphic graph.

asked Jan 21 in Set Theory & Algebra by Nandkishor3939 Active (1.2k points) | 38 views

0 votes

1 answer

20

MadeEasy Test Series: Discrete Mathematics - Graph Thoery
The number of labelled subgraphs possible for the graph given below.

asked Jan 19 in Graph Theory by snaily16 (263 points) | 252 views

0 votes

0 answers

21

Algorithm questions on graphs
let Gn be a complete graph on n vertices where n>2 such that each vertex is labeled by a distinct number 1,2, 3, 4, …, n , and each edge is labeled by the sum of its endpoint labels. Let f(Gn) be the minimum sum of edge labels in any path that touches every vertex in exactly once. How many values of satisfy f(Gn)2013 (mod n) ?___________

asked Jan 19 in Algorithms by Iamniks4 (63 points) | 23 views

0 votes

0 answers

22

Ace Test Series: Graph Theory - Cut Edges
If G is a connected simple graph with 10 vertices in which degree of every vertex is 2 then number of cut edges in G is ?

asked Jan 19 in Graph Theory by Na462 Loyal (8.7k points) | 74 views

0 votes

1 answer

23

ME test series question on graph theory

asked Jan 17 in Graph Theory by Shankar Kakde (373 points) | 63 views

0 votes

2 answers

24

Applied Course 2019 Mock1-36
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends ... distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$

asked Jan 16 in Graph Theory by Applied Course Junior (797 points) | 89 views

0 votes

0 answers

25

Made Easy
What are all the conditions for the degree sequence to be graphic?

asked Jan 16 in Algorithms by gate_dreams (329 points) | 38 views

+1 vote

2 answers

26

MadeEasy Subject Test 2019: Graph Thoery - Graph Coloring
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None

asked Jan 16 in Graph Theory by Na462 Loyal (8.7k points) | 78 views

+1 vote

1 answer

27

MadeEasy Full Length Test 2019: Graph Theory - Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None

asked Jan 16 in Graph Theory by Na462 Loyal (8.7k points) | 82 views

+2 votes

1 answer

28

How many Binary Search Trees are possible for a labelled nodes?
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?

asked Jan 16 in DS by sripo Active (2.6k points) | 206 views

0 votes

0 answers

29

MadeEasy Full Length Test 2018: Graph Theory - Counting
The Number of Labelled possible graph given below ? what I did was → we doesn't remove any of the edge out of 4 = $\binom{4}{0}$ [Because a Graph is sub-graph of itself] we can remove any of one edge out of 4 = $\binom{4}{1}$ we can remove any ... out of 4 = $\binom{4}{2}$ similarly , $\binom{4}{3}$ , $\binom{4}{4 }$ then , add of the them

asked Jan 15 in Graph Theory by Magma Boss (13.8k points) | 88 views

0 votes

1 answer

30

CUT VERTEX
plz solve this problem..

asked Jan 9 in Mathematical Logic by Vikas123 (367 points) | 62 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged graph-theory

Recent Posts

Recent Blog Comments