search
Log In

Recent questions tagged graph-theory

0 votes
1 answer
1
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
asked Mar 30 in Graph Theory Lakshman Patel RJIT 97 views
0 votes
3 answers
2
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
asked Mar 30 in Graph Theory Lakshman Patel RJIT 203 views
0 votes
1 answer
3
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above
asked Mar 24 in Graph Theory jothee 85 views
6 votes
3 answers
4
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______
asked Feb 12 in Graph Theory Arjun 1.7k views
0 votes
3 answers
5
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$
asked Feb 11 in Graph Theory Lakshman Patel RJIT 140 views
2 votes
1 answer
6
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match requires a ... to solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked Sep 13, 2019 in Graph Theory gatecse 158 views
4 votes
2 answers
7
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
asked Sep 13, 2019 in Graph Theory gatecse 146 views
0 votes
1 answer
8
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked Sep 13, 2019 in Graph Theory gatecse 106 views
1 vote
1 answer
9
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
asked Sep 13, 2019 in Graph Theory gatecse 99 views
1 vote
0 answers
10
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ ... which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
asked Sep 13, 2019 in Graph Theory gatecse 69 views
3 votes
2 answers
11
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$
asked Jul 2, 2019 in Graph Theory Arjun 529 views
0 votes
1 answer
12
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
asked Jun 2, 2019 in Algorithms srestha 135 views
2 votes
1 answer
13
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ $m$ $=$ $n$ ... $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.
asked May 26, 2019 in Graph Theory `JEET 138 views
1 vote
2 answers
14
Which of the following is not true? (a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in $G$ (c) Number of ... $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.
asked May 26, 2019 in Graph Theory `JEET 371 views
1 vote
1 answer
15
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$ ... $x$ 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 May 23, 2019 in Graph Theory srestha 240 views
5 votes
0 answers
16
Prove that the rank of the Adjacency Matrix which is associated with a $k-$ regular graph is $k.$
asked May 22, 2019 in Graph Theory ankitgupta.1729 180 views
1 vote
2 answers
17
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
asked May 19, 2019 in Graph Theory Hirak 287 views
0 votes
2 answers
18
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, 2019 in Graph Theory chandan2teja 164 views
0 votes
3 answers
19
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, 2019 in DS manikgupta123 394 views
1 vote
1 answer
20
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, 2019 in Graph Theory gmrishikumar 159 views
0 votes
0 answers
21
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, 2019 in Graph Theory akash.dinkar12 121 views
0 votes
0 answers
22
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, 2019 in Graph Theory noxevolution 71 views
0 votes
0 answers
23
What is meant by edge disjoint hamiltonian circuits in a graph
asked Mar 5, 2019 in Graph Theory Winner 133 views
2 votes
0 answers
24
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, 2019 in Graph Theory Sayan Bose 149 views
13 votes
9 answers
25
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, 2019 in Graph Theory Arjun 6.1k views
14 votes
6 answers
26
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, 2019 in Graph Theory Arjun 5.9k views
1 vote
0 answers
27
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 an edge cover of 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, 2019 in Graph Theory Ashish Goyal 207 views
0 votes
2 answers
28
A simple regular graph n vertices and 24 edges, find all possible values of n.
asked Jan 29, 2019 in Graph Theory amit166 171 views
0 votes
0 answers
30
Number of labelled subgraphs possible for the graph given below______________
asked Jan 25, 2019 in DS Nandkishor3939 151 views
...