Recent questions and answers in 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_____________

answered 18 hours ago in Graph Theory by Satbir Loyal (8.1k 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

answered 4 days ago in Graph Theory by srestha Veteran (114k points) | 53 views

+1 vote

2 answers

4

CMI2011-B-01b
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. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.

answered 4 days ago in Graph Theory by Arjun Veteran (400k points) | 122 views

+1 vote

2 answers

5

GATE1989-4-vii
Provide short answers to the following questions: In the graph shown above, the depth-first spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.

answered 6 days ago in Graph Theory by Arjun Veteran (400k points) | 262 views

0 votes

1 answer

6

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.

answered 6 days ago in Graph Theory by pdeshal (11 points) | 37 views

0 votes

0 answers

7

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

+1 vote

7 answers

8

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}$

answered Apr 26 in Graph Theory by gaurav1.yuva (403 points) | 2.7k views

0 votes

0 answers

9

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

10

self-doubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??

asked Mar 31 in Graph Theory by Doraemon (203 points) | 13 views

0 votes

0 answers

11

self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??

asked Mar 31 in Graph Theory by Doraemon (203 points) | 34 views

+18 votes

5 answers

12

TIFR2010-B-36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.

answered Mar 29 in Graph Theory by Debargha Bhattacharj (225 points) | 1k views

0 votes

1 answer

13

Allen Career Institute: Spanning tree
Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, . 99.}$ Weight of the edge $(u, v)$ is $\left | u-v \right |$ where $0\leq u, v\leq 99$ and $u\neq v$. Weight ... tree is______________ Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.

answered Mar 29 in Graph Theory by ankitgupta.1729 Boss (11.4k points) | 66 views

0 votes

1 answer

14

Allen Career Institute:Graph Theory
If G be connected planar graph with 12 vertices of deg 4 each. In how many regions can this planar graph be partitioned?

answered Mar 28 in Graph Theory by abhishekmehta4u Boss (33.6k points) | 47 views

+32 votes

6 answers

15

GATE2014-3-51
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$

answered Mar 27 in Graph Theory by Ashish Kumar Choubey (35 points) | 4.1k views

+33 votes

5 answers

16

GATE2006-IT-25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$

answered Mar 20 in Graph Theory by Kuljeet Shan Active (1.3k points) | 2.6k views

0 votes

0 answers

17

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

+1 vote

1 answer

18

Zeal Test Series 2019: Graph Theory - Graph Matching

answered Mar 7 in Graph Theory by abhishekmehta4u Boss (33.6k points) | 67 views

0 votes

0 answers

19

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

+1 vote

1 answer

20

Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example - If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.

answered Feb 22 in Graph Theory by saurav raghaw Active (1.4k points) | 446 views

+2 votes

1 answer

21

GATE - 2014 - 1- 51 modified
Consider an directed graph G where self-loops are not allowed. The vertex set of G is {(i,j)∣1≤i≤12,1≤j≤12}There is an edge from(a,b) to (c,d) if |a−c|≤1 and |b−d|≤1. The number of edges in this graph is______

answered Feb 18 in Graph Theory by Priyadrasta Raut (373 points) | 133 views

0 votes

0 answers

22

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

0 votes

0 answers

23

JEST 2019 Descriptive Q2 (8 Marks)
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decreasing subsequence of length n+1.

asked Feb 17 in Graph Theory by dan31 Junior (877 points) | 72 views

0 votes

0 answers

24

JEST 2019 Descriptive Q1 (8 Marks)
Suppose that G contains a cycle C, and a path of length at least k between some two vertices of C. Show that G contains a cycle of length at least √k.

asked Feb 17 in Graph Theory by dan31 Junior (877 points) | 48 views

+12 votes

3 answers

25

CMI2013-A-06
A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$

answered Feb 15 in Graph Theory by Satbir Loyal (8.1k points) | 610 views

+21 votes

8 answers

26

GATE2017-2-23
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .

answered Feb 8 in Graph Theory by Suneel Padala Junior (841 points) | 4.3k views

+1 vote

1 answer

27

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

answered Feb 7 in Graph Theory by Digvijay Pandey Veteran (59.7k points) | 2.3k views

0 votes

1 answer

28

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!

answered Feb 7 in Graph Theory by Sahil Arora 2 (15 points) | 324 views

0 votes

2 answers

29

GATE2019
What is the total number of different Hamiltonian cycles for the complete graph of n vertices?

answered Feb 3 in Graph Theory by Sumit Rana 1 Junior (819 points) | 728 views

0 votes

0 answers

30

Abelian group
A quick question Is every multiplication modulo function a Abelian group....Or is it the case that the function should have prime number as modulo

asked Feb 2 in Graph Theory by Nandkishor3939 Active (1.2k points) | 36 views

0 votes

4 answers

31

GateForum Test Series: Graph Theory - Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____

answered Feb 1 in Graph Theory by Sai Shravan (169 points) | 342 views

0 votes

0 answers

32

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

0 answers

33

Madeeasy
A graph G is called self complementary iff G is isomorphic to its complement. Let X be a self complementary graph. Which of the following is a viable possibility with regards to the connectivity of X and X', where X' denotes the complement of X, ... answer such questions. So the conclusion is "Every sell complementary graph is cormected". So option (d) is the correct answer.

asked Jan 29 in Graph Theory by mehul vaidya Active (4.4k points) | 26 views

0 votes

0 answers

34

selfdoubt-ME-testseries
we define a new measure ,called GoldIndex(G,C).it takes two arguments as input namely a graph G and set of colors C respectively . the subroutine outputs an integer denoting the number of ways assigning colors to vertices in G such that at least two vertices ... 't know where m i going wrong ,please help me- i know their solution is correct but i want to verify my approach- [closed]

asked Jan 29 in Graph Theory by Prateek Raghuvanshi Boss (10.2k points) | 65 views

0 votes

1 answer

35

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

answered Jan 29 in Graph Theory by prashant jha 1 Loyal (5.4k points) | 70 views

0 votes

0 answers

36

max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure

asked Jan 26 in Graph Theory by Nandkishor3939 Active (1.2k points) | 84 views

0 votes

0 answers

37

Made Easy Practice Book
The number of labelled subgraph possible for the graph given below are ________.

asked Jan 25 in Graph Theory by Shankar Kakde (373 points) | 36 views

0 votes

1 answer

38

ACE TEST SERIES QUESTION ON Graph Theory

answered Jan 25 in Graph Theory by soubhik baral (229 points) | 41 views

0 votes

0 answers

39

Counting

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

0 votes

1 answer

40

ACE Test series question on Chromatic number

answered Jan 25 in Graph Theory by Sai Shravan (169 points) | 50 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 and answers in Graph Theory

Recent Posts

Recent Blog Comments