Recent questions and answers in Graph Theory - GATE Overflow

First time here? Checkout the FAQ!

x

0 votes

2 answers

1

PGEE 2018
Maximal Independence Number is the cardinality of maximal independence set ( Independence set V of graph G is set in which no vertex of the set have a direct edge between them). 1) Maximal Independence Number of a complete graph is n-1 2) Maximal Independence ... Maximal Independence Number of a complete graph is 1 4) Maximal Independence Number of complete graph is $\geq \frac{n}{2}$

answered 6 hours ago in Graph Theory by abhishekmehta4u Loyal (9.7k points) | 21 views

+1 vote

1 answer

2

PGEE 2018
Consider Undirected Graph G having vertex V {A,B,C,D,E} and edge pair as E {AB BD BE AC CE CD} A) Given graph is disconnected B) Given graph is complete C) Given graph has vertex connectivity 2 D) Given graph has edge connectivity 1

answered 6 hours ago in Graph Theory by abhishekmehta4u Loyal (9.7k points) | 17 views

0 votes

1 answer

3

IIT Kanpur Sample Test Paper
Given an undirected graph with vertices as your friends and edges between people who do not talk to each other. Your task is to invite as many guests to your party such that there are no two friends at the party who have problem talking to each ... instance of: A. Maximum vertex cover. B. Maximum cut. C. Maximum eigenvalue of adjacency matrix. D. None of the above.

answered 4 days ago in Graph Theory by Mk Utkarsh Boss (11.9k points) | 53 views

+1 vote

1 answer

4

CMI2010-A-06
A simple graph is one with no self-loops or multiple edges. Among the simple graphs with n vertices and at most 20n − 3 edges: There is always a graph with all vertices connected to at least 42 other vertices. For all such graphs the number of ... for some constant $c < 1$. There are no graphs with each vertex connected to at most 38 other vertices. None of the above

answered 4 days ago in Graph Theory by Mk Utkarsh Boss (11.9k points) | 86 views

0 votes

2 answers

5

CMI2017-B-5
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has degree 1. Prove that ... -that is, u ∈ V1 and v ∈ V2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.

answered 5 days ago in Graph Theory by Mk Utkarsh Boss (11.9k points) | 85 views

+1 vote

1 answer

6

Narsingh Deo Problem 2-28

answered 5 days ago in Graph Theory by Kushagra Chatterjee Junior (827 points) | 46 views

+9 votes

2 answers

7

TIFR2018-A-9
How many ways are there to assign colours from range $\left\{1,2,...,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$

answered 5 days ago in Graph Theory by Sourav Basu Active (1.4k points) | 278 views

+14 votes

6 answers

8

TIFR2015-B-5
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency matrix of an ... below has the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$

answered 6 days ago in Graph Theory by Hitesh (369 points) | 572 views

0 votes

1 answer

9

Show that the two graphs are isomorphic (Narsingh Deo)

answered 6 days ago in Graph Theory by Hitesh (369 points) | 16 views

+1 vote

1 answer

10

What are the relevant chapters for GATE from the Graph Theory book by Narsingh Deo?

answered 6 days ago in Graph Theory by Mk Utkarsh Boss (11.9k points) | 107 views

+1 vote

1 answer

11

Graph Theory
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.

answered 6 days ago in Graph Theory by Kushagra Chatterjee Junior (827 points) | 13 views

+28 votes

4 answers

12

GATE2006-71
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$

answered Apr 14 in Graph Theory by JPranavc (225 points) | 2.7k views

+1 vote

3 answers

13

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

answered Apr 13 in Graph Theory by Sandy Sharma (235 points) | 200 views

+3 votes

2 answers

14

True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.

answered Apr 12 in Graph Theory by Digvijay Pandey Veteran (54.7k points) | 79 views

0 votes

0 answers

15

Number of Possible Trees
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?

asked Apr 11 in Graph Theory by ankitgupta.1729 Active (4.2k points) | 17 views

+1 vote

1 answer

16

CMI2011-B-01a
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road ... it always possible to colour each building with either red or blue so that every road connects a red and blue building?

answered Apr 11 in Graph Theory by Kushagra Chatterjee Junior (827 points) | 51 views

+1 vote

1 answer

17

CMI2011-B-02b
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Given a good graph, devise a linear time algorithm to find two such vertices.

answered Apr 11 in Graph Theory by Kushagra Chatterjee Junior (827 points) | 62 views

+2 votes

1 answer

18

CMI2010-B-02
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.

answered Apr 9 in Graph Theory by Kushagra Chatterjee Junior (827 points) | 62 views

+2 votes

1 answer

19

CMI2010-B-01a
An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least 100 km apart, so that there is no interference of signals. Model this problems using graphs.

answered Apr 9 in Graph Theory by Kushagra Chatterjee Junior (827 points) | 35 views

0 votes

1 answer

20

#Graph Theory Any Simple way to prove this ?

answered Apr 9 in Graph Theory by asriv Active (1.1k points) | 50 views

+1 vote

1 answer

21

Discrete Mathematics By Kenneth H Rosen
How to Find Whether Given Graph is NonPlanar using Kuratwoski's Theorem ?

answered Apr 6 in Graph Theory by Hitesh (369 points) | 27 views

0 votes

1 answer

22

Graph Theory
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? $cost(a,b)\geq 6$. $cost(b,e)\geq 5$. $cost(e,f)\geq 5$. $cost(a,d)\geq 4$. $cost(b,c)\geq 4$. Please someone solve and explain :)

answered Apr 6 in Graph Theory by abhishekmehta4u Loyal (9.7k points) | 54 views

+1 vote

1 answer

23

Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithms-time-complexity

answered Apr 5 in Graph Theory by abhishekmehta4u Loyal (9.7k points) | 50 views

0 votes

1 answer

24

related to gate previous year
can some give example where cardinality of min-cut will be < min-degree of the graph I found in question they have mentioned its <= , but i dont see any case where it is < https://gateoverflow.in/1504/gate1999_5 [closed]

answered Apr 5 in Graph Theory by Ananya Jaiswal 1 Active (1.2k points) | 17 views

+5 votes

3 answers

25

GATE1992_02,viii
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only: (viii) A non-planar graph with minimum number of vertices has (a) 9 edges, 6 vertices (b) 6 edges, 4 vertices (c) 10 edges, 5 vertices (d) 9 edges, 5 vertices

answered Apr 3 in Graph Theory by sourav. Boss (15.8k points) | 414 views

+23 votes

2 answers

26

GATE2001-2.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $

answered Apr 1 in Graph Theory by mehul vaidya Junior (593 points) | 2.3k views

+1 vote

1 answer

27

UGC NET NOV 2017 PAPER 2 Q-5
5. Consider the graph given below : Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is ? (1) AD, AE, AG, GC, GB, BF (2) GC, GB, BF, GA, AD, AE (3) GC, AD, GB, GA, BF, AE (4) AD, AG, GC, AE, GB, BF

answered Mar 30 in Graph Theory by Sukanya Das Boss (11.2k points) | 89 views

0 votes

0 answers

28

Graph Theory By Narsingh Deo
Where can I find solutions to Narsingh Deo Book for Graph theory any online links and pdf will be helpful ?

asked Mar 26 in Graph Theory by Sayed Athar (93 points) | 45 views

+21 votes

4 answers

29

TIFR2017-B-12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$

answered Mar 26 in Graph Theory by Pawan Kumar 2 Active (4.4k points) | 918 views

0 votes

0 answers

30

Graph Theory
Walk : Vertices may repeat. Edges may repeat (Closed or Open) Trail : Vertices may repeat. Edges cannot repeat (Open) Circuit : Vertices may repeat. Edges cannot repeat (Closed) Path : Vertices cannot repeat. Edges cannot repeat (Open) Cycle : Vertices cannot repeat. Edges cannot repeat (Closed) Can someone verify these terminologies? They are pretty confusing :/

asked Mar 26 in Graph Theory by gauravkc Active (4.9k points) | 45 views

+1 vote

1 answer

31

Graph theory
As a triangle graph is $2 -$ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can someone tell me where did I go wrong? Thanks

answered Mar 25 in Graph Theory by abhishekmehta4u Loyal (9.7k points) | 84 views

0 votes

0 answers

32

[Graphs]IIT-k Written test
Graph Matching was explained. Let $S$ and $R$ be the matching graph, then a new graph $G=(S-R) \cup (R-S)$, will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.

asked Mar 19 in Graph Theory by rahul sharma 5 Boss (23k points) | 67 views

+2 votes

0 answers

33

[Graphs]IIT-k Written test
if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle

asked Mar 19 in Graph Theory by rahul sharma 5 Boss (23k points) | 61 views

0 votes

1 answer

34

Rosen (Graph)
Show that an edge in a simple graph is a cut edge if and only if this edge is not a part of any simple circuit in the graph.

answered Mar 18 in Graph Theory by Kaluti Loyal (5.3k points) | 49 views

0 votes

1 answer

35

GraphTheory_Problem_testpaper
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bits of strings of length $n$. We have an edge between vertex $u$ and $v$ if and only if $u$ and $v$ differ exactly in one bit position. The ratio of chromatic number of $G$ to the diameter of $G$ is . $\dfrac{1}{(2^{n-1})}$ $\dfrac{1}{n}$ $\dfrac{2}{n}$ $\dfrac{3}{n}$ [closed]

answered Mar 17 in Graph Theory by Kaluti Loyal (5.3k points) | 57 views

+1 vote

1 answer

36

Graph Theory: Degree of a region
In the given following planar graph, what is the degree of the region R1:

answered Mar 12 in Graph Theory by MayankSharma (121 points) | 178 views

+7 votes

5 answers

37

GATE2018-18
The chromatic number of the following graph is _____

answered Mar 8 in Graph Theory by Sukanya Das Boss (11.2k points) | 1.2k views

0 votes

0 answers

38

UGC NET DEC 14 PAPER 2 Q - 45
45. Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions – 1 (B) E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) P – 1, where P is the number of predicate nodes in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G. [closed]

asked Mar 8 in Graph Theory by kavikeve (459 points) | 42 views

0 votes

3 answers

39

Planar graph
The total number of planar graphs can be formed with 5 vertices are _____

answered Mar 6 in Graph Theory by Mk Utkarsh Boss (11.9k points) | 204 views

0 votes

1 answer

40

Rosen (Graphs)
How much storage is needed to represent a simple graph with n vertices and m edges using. a) adjacency lists? b) an adjacency matrix? c) an incidence matrix?

answered Mar 1 in Graph Theory by Tesla! Boss (15.3k points) | 89 views

To see more, click for all the questions in this category.

Follow @csegate

Gatecse

Recent questions and answers in Graph Theory

34,814 questions

41,801 answers

119,032 comments

41,445 users