Recent questions tagged graph-theory

0 votes

0 answers

1

GATEBOOK-2019-DS2-1
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? 7, 5, 5, 3, 3, 2, 2, 2 6, 6, 6, 6, 3, 3, 2, 2, 1, 1 8, 7, 6, 4, 4, 3, 2, 2, 2 8, 7, 6, 6, 4, 4, 2, 2, 2 II and III III and IV IV only I and IV

asked 2 days ago in Programming by GATEBOOK (471 points) | 19 views

0 votes

1 answer

2

GATEBOOK-2019-DS2-3
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with $10$ vertices, where cardinalities of those five sets are given as $\{2,3,2,1,2\},$ is: $16$ $20$ $26$ $39$

asked 2 days ago in Programming by GATEBOOK (471 points) | 23 views

0 votes

0 answers

3

virtual gate graph theory
i am getting 6 as answer

asked 3 days ago in Graph Theory by Prince Sindhiya Active (3.6k points) | 49 views

0 votes

1 answer

4

Complete Matching
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083

asked 5 days ago in Mathematical Logic by Na462 Loyal (6.4k points) | 28 views

+2 votes

2 answers

5

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? $A)$ Vertex $n$ has degree ... connected $C)$ There is a path from vertex $1$ to vertex $n$ $D)$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Loyal (9.6k points) | 51 views

0 votes

1 answer

6

Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Loyal (9.6k points) | 45 views

0 votes

1 answer

7

Complete Graph
Consider the following graph: Number of the Hamiltonian cycles starting and ending point at $ A$ is _______

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Loyal (9.6k points) | 64 views

0 votes

0 answers

8

Mathematics

asked Oct 4 in Set Theory & Algebra by jatinkumar (223 points) | 21 views

0 votes

0 answers

9

Made easy,graphs
let G be an undirected graph. consider a depth-first traversal of G, and let T be the resulting depth-first search tree. let you be a vertex in G and let V be the first new (unvisited) vortex visited after visiting you in the traversal. which of the following statement is always true?

asked Oct 1 in DS by KrishY (7 points) | 39 views

+1 vote

0 answers

10

UGC-NET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21

asked Sep 28 in Graph Theory by aditi19 Junior (863 points) | 25 views

0 votes

0 answers

11

Can Null Graph be a valid Matching
Definition of valid matching says that if every vertex is incident with atmost one vertex then it is a matching but I have seen coaching material note which includes null graph as a matching.I am confused please help.

asked Sep 28 in Graph Theory by sripo (293 points) | 8 views

0 votes

0 answers

12

General query of Graph Theory
$1)$ Is there any general formula for maximum degree (if possible also minimum degree) of a vertex in a graph G? $2)$ Is there any relationship between indegree and outdegree of a graph?

asked Sep 25 in Graph Theory by srestha Veteran (98.4k points) | 30 views

0 votes

1 answer

13

Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________.

asked Sep 21 in Graph Theory by srestha Veteran (98.4k points) | 63 views

0 votes

0 answers

14

Bipartite Graph
Which of the following complete bipartite graphs will have Hamiltonian cycle? $a)K_{3,3}$ $b)K_{2,4}$

asked Sep 21 in Graph Theory by srestha Veteran (98.4k points) | 53 views

0 votes

1 answer

15

Graph Theory
Please help with the following:- 1)How to determine if a graph is bipartite or not? 2)What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?

asked Sep 18 in Graph Theory by Devshree Dubey Boss (13.6k points) | 21 views

0 votes

2 answers

16

ME test series.
How 14? I am not able to understand. Why not 30.

asked Sep 6 in Graph Theory by aoao (77 points) | 73 views

0 votes

0 answers

17

Doubt
What is converse of a graph?

asked Sep 1 in Graph Theory by aditi19 Junior (863 points) | 15 views

0 votes

1 answer

18

GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?

asked Aug 31 in Mathematical Logic by Nidhi Budhraja (121 points) | 38 views

+2 votes

1 answer

19

Graph theory
Stmt 1: A simple graph is necessarily connected if |E| > (n-1)*(n-2)/2. Stmt2: A simple graph with n vertices and k components has at least n-k edges. Can you please explain how are these results derived?

asked Aug 26 in Mathematical Logic by Nidhi Budhraja (121 points) | 65 views

+1 vote

0 answers

20

Kenneth Rosen Discrete Mathematics
DIRAC’S THEOREM: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. The below graph does not follow the above rule but still have a Hamilton circuit.

asked Aug 25 in Graph Theory by CJ147 (73 points) | 28 views

+1 vote

1 answer

21

Number of Eulerian Graphs
Find the number of connected Eulerian graphs with 6 unlabelled vertices. Draw each of them. Note: I'm looking for a fast procedure don't comment just the numerical answer.

asked Aug 24 in Graph Theory by Mk Utkarsh Boss (20.1k points) | 55 views

0 votes

0 answers

22

Cosets subgraphs legranges thm
I am not able to understand clearly the concepts related to cosets, subgroups, lattice theory.Can someone suggest references to clarify my understanding of each topic?

asked Aug 22 in Mathematical Logic by Nidhi Budhraja (121 points) | 11 views

0 votes

1 answer

23

Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?

asked Aug 13 in Algorithms by Sambhrant Maurya Junior (755 points) | 57 views

+1 vote

2 answers

24

Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m

asked Aug 13 in Graph Theory by srestha Veteran (98.4k points) | 144 views

0 votes

1 answer

25

Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.

asked Aug 11 in Algorithms by Prince Sindhiya Active (3.6k points) | 17 views

0 votes

0 answers

26

Show that T is a maximum spanning tree for G

asked Jul 24 in Graph Theory by abram19000 (7 points) | 31 views

0 votes

1 answer

27

ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.

asked Jul 24 in Graph Theory by abhishek1995_cse (131 points) | 97 views

+1 vote

1 answer

28

ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.

asked Jul 24 in Graph Theory by abhishek1995_cse (131 points) | 51 views

0 votes

1 answer

29

me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?

asked Jul 17 in Graph Theory by ronin_codex (7 points) | 56 views

0 votes

0 answers

30

graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.

asked Jul 14 in Graph Theory by poojasharma123 (89 points) | 77 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