Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
0
votes
1
answer
511
Graph theory.
Matching and edge coloring are same ?
Matching and edge coloring are same ?
elakashi sharma
876
views
elakashi sharma
asked
Aug 19, 2017
Graph Theory
graph-theory
+
–
0
votes
1
answer
512
Consider the following graph L and find the bridges, if any
A) No bridge B) {d, e} C) {c, d} D) {c, d} and {c, f}
A) No bridgeB) {d, e}C) {c, d}D) {c, d} and {c, f}
habedo007
2.3k
views
habedo007
asked
Aug 18, 2017
DS
graph-theory
bridges
+
–
2
votes
1
answer
513
Min Cut set
Beyonder
578
views
Beyonder
asked
Aug 17, 2017
Graph Theory
graph-theory
min-cut
discrete-mathematics
+
–
1
votes
0
answers
514
Please solve this Q
Q. Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} g is given by the entry Wij in the matrix WThe largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ________ Note : This question was asked as Numerical Answer Type. A) 8 B) 12 C) 10 D) 11
Q. Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} g is given by the entry Wij in the matrix WThe largest possible integer value ...
kallu singh
401
views
kallu singh
asked
Aug 17, 2017
Algorithms
algorithms
graph-theory
+
–
1
votes
1
answer
515
please solve this Q
Q . The maximum number of edges in an undirected graph (simple) with 52 vertices and 3 components are
Q . The maximum number of edges in an undirected graph (simple) with 52 vertices and 3 components are
kallu singh
1.0k
views
kallu singh
asked
Aug 8, 2017
Graph Theory
graph-theory
+
–
2
votes
0
answers
516
Kenneth Rosen Edition 6th Exercise 8.4 Question 17 (Page No. 575)
Find the number of paths of length n between two different vertices in K4 if n is a) 2. b) 3. c) 4. d) 5.
Find the number of paths of length n between two different vertices in K4 if n isa) 2. b) 3. c) 4. d) 5.
reena_kandari
1.2k
views
reena_kandari
asked
Aug 8, 2017
Graph Theory
kenneth-rosen
discrete-mathematics
graph-theory
+
–
2
votes
1
answer
517
Graph
The problem of finding the set of vertices reachable from a given vertex in a graph can be solved in time A. O(|V|^2) B. O(|V| + |E|) C. O(|V||E|) D. none of these
The problem of finding the set of vertices reachable from a given vertex in a graph can be solved in timeA. O(|V|^2)B. O(|V| + |E|)C. O(|V||E|)D. none of these
Abhisek Saha
537
views
Abhisek Saha
asked
Jul 15, 2017
Algorithms
graph-theory
graph-algorithms
+
–
1
votes
2
answers
518
maximum value of n to be deadlock
A computer system has 6 tape drives, with n processes competing for them. Each process may need 3 tape drives. What is the maximum value of n for which the system is guaranteed to be deadlock? Justify your answer.
A computer system has 6 tape drives, with n processes competing for them. Each process may need 3 tape drives. What is the maximum value of n for which the system is guar...
Xuan Eric
2.9k
views
Xuan Eric
asked
Jul 14, 2017
Operating System
graph-theory
+
–
1
votes
2
answers
519
graph theory
can we say a null graph is eulerian circuit and hamiltonian circuit?
can we say a null graph is eulerian circuit and hamiltonian circuit?
akankshadewangan24
822
views
akankshadewangan24
asked
Jul 8, 2017
Mathematical Logic
graph-theory
graph-connectivity
+
–
2
votes
3
answers
520
Kenneth Rosen Edition 7 Exercise 10.8 Question 23 (Page No. 734)
Find the edge chromatic numbers of a) Cn, where n ≥ 3. (Cycle with n vertices) b) Wn, where n ≥ 3 (Wheel with n vertices) c)Complete graph with n vertices.
Find the edge chromatic numbers ofa) Cn, where n ≥ 3. (Cycle with n vertices)b) Wn, where n ≥ 3 (Wheel with n vertices)c)Complete graph with n vertices.
Soumya29
3.7k
views
Soumya29
asked
Jul 8, 2017
Graph Theory
discrete-mathematics
kenneth-rosen
graph-theory
+
–
1
votes
1
answer
521
graph
a tree with n vertices can have at most 1 perfect matching how? perfect matching means no vertices will be left with 0 dergree right so how a tree can have a perfect matching explain with the help of trees plz
a tree with n vertices can have at most 1 perfect matching how? perfect matching means no vertices will be left with 0 dergree right so how a tree can have a perfect mat...
akankshadewangan24
466
views
akankshadewangan24
asked
Jul 5, 2017
Mathematical Logic
graph-theory
+
–
2
votes
0
answers
522
Graph Degree sequence : Bondy and Murty : $1.1.16$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that: there is a loopless graph with degree sequence d if and only if $\sum_{i=1}^{n}d_i$ is even and $d_1 \leq \sum_{i=2}^{n}d_i$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that:there is a loopless g...
dd
429
views
dd
asked
Jul 4, 2017
Graph Theory
graph-theory
non-gate
proof
degree-of-graph
+
–
1
votes
0
answers
523
Graph Theory : Bondy-Murty $1.1.20$
Let $S$ be a set of $n$ points in the plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of S at distance exactly one. Can this be done with a unit circle and we can place at max. $6$ points on the perimeter and doing the same for other points as well ? i.e. we can get $6n/2 = 3n$ pairs at max. ?
Let $S$ be a set of $n$ points in the plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of S at distance exac...
dd
306
views
dd
asked
Jul 4, 2017
Graph Theory
graph-theory
non-gate
proof
+
–
2
votes
0
answers
524
Graphic Sequence condition
A sequence $d = (d_1,d_2,\dots , d_n)$ is graphic if there is a simple graph with degree sequence $d$ If $d = (d_1,d_2,d_3, \dots d_n)$ is graphic and $d_1 \geq d_2 \geq d_3 \geq \dots \geq d_n$ , then show that $\sum_{i=1}^{n}d_i$ is even and $\sum_{i=1}^{k}d_i \leq \left [ k(k-1) + \sum_{i=k+1}^{n} \min\{k,d_i\} \right ] \quad ,1 \leq k \leq n$.
A sequence $d = (d_1,d_2,\dots , d_n)$ is graphic if there is a simple graph with degree sequence $d$If $d = (d_1,d_2,d_3, \dots d_n)$ is graphic and $d_1 \geq d_2 \geq d...
dd
389
views
dd
asked
Jul 4, 2017
Graph Theory
non-gate
graph-theory
proof
+
–
3
votes
0
answers
525
Minimum No. of vertices required
Prove the following for graph $G$. When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ ... $k$.
Prove the following for graph $G$.When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ has minimum $\begin{alig...
dd
371
views
dd
asked
Jul 1, 2017
Graph Theory
graph-theory
proof
+
–
0
votes
1
answer
526
Diameter of a graph and tree
Why there is a difference between diameter of a graph and tree? Diameter of a tree as i have read is the maximum path between two vertices(number of edges between two vertices) But for tree it says number of nodes on the longest path. But tree is a graph so why cant i find the diameter of tree in similar way?
Why there is a difference between diameter of a graph and tree?Diameter of a tree as i have read is the maximum path between two vertices(number of edges between two vert...
rahul sharma 5
660
views
rahul sharma 5
asked
Jun 19, 2017
Mathematical Logic
graph-theory
algorithms
+
–
0
votes
1
answer
527
Self - Doubt
What is clique?
What is clique?
Arnab Bhadra
212
views
Arnab Bhadra
asked
Jun 19, 2017
Graph Theory
graph-theory
+
–
3
votes
3
answers
528
[Discrete Maths] Graph Theory Rosen,Chromatic number
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?
What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?
rahul sharma 5
1.9k
views
rahul sharma 5
asked
Jun 12, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
graph-coloring
+
–
0
votes
0
answers
529
Kenneth Rosen Edition 6th Exercise 8.6 Question 47 a (Page No. 590)
How is the following graph is Hamilton?The answer says it has Hamilton circuit .
How is the following graph is Hamilton?The answer says it has Hamilton circuit.
rahul sharma 5
725
views
rahul sharma 5
asked
Jun 12, 2017
Mathematical Logic
discrete-mathematics
kenneth-rosen
graph-theory
+
–
2
votes
2
answers
530
Discrete Maths Graph theory
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
rahul sharma 5
2.0k
views
rahul sharma 5
asked
Jun 12, 2017
Mathematical Logic
graph-theory
discrete-mathematics
graph-connectivity
+
–
0
votes
1
answer
531
[Discrete maths] graph theory Perfect matching
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me ... but still it is not a perfect match?I am not able to find such a case and i think it will not exist.
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching an...
rahul sharma 5
1.1k
views
rahul sharma 5
asked
Jun 8, 2017
Mathematical Logic
graph-theory
graph-matching
+
–
3
votes
1
answer
532
[Discrete Maths] Graph theory
What is the vertex connectivity and edge connectivity of complete graph? Is it n or n-1?
What is the vertex connectivity and edge connectivity of complete graph?Is it n or n-1?
rahul sharma 5
1.3k
views
rahul sharma 5
asked
Jun 7, 2017
Graph Theory
discrete-mathematics
graph-theory
graph-connectivity
+
–
0
votes
2
answers
533
iisc written
Consider a directed graph with V nodes and E edges. The graph is represented by two arrays, source src[] and destination dest[] each of size E, such that src[i] and dest[i] represent the nodes connected by edge, i. How to calculate the maximum indegree(or out degree)?
Consider a directed graph with V nodes and E edges. The graph is represented by two arrays, sourcesrc[] and destination dest[] each of size E, such that src[i] and dest[i...
Purple
530
views
Purple
asked
Jun 6, 2017
Graph Theory
graph-theory
graph-connectivity
iisc-interview
iisc
mtech
descriptive
+
–
0
votes
2
answers
534
Graphs
Maximum degree of any vertex in a single graph of vertices n is? a. none of the above b. n c. n-1 d. n+1 e. 2n-1
Maximum degree of any vertex in a single graph of vertices n is?a. none of the aboveb. nc. n-1d. n+1e. 2n-1
quevon24
5.1k
views
quevon24
asked
May 25, 2017
Programming in C
graph-theory
+
–
5
votes
2
answers
535
Test by Bikram | Mathematics | Test 2 | Question: 5
Let $G$ be a graph of order $8$ in which every vertex has equal degree $D$. In order to guarantee that $G$ is connected, the minimum value of $D$ must be ____________
Let $G$ be a graph of order $8$ in which every vertex has equal degree $D$. In order to guarantee that $G$ is connected, the minimum value of $D$ must be ____________
Bikram
714
views
Bikram
asked
May 24, 2017
Graph Theory
tbb-mathematics-2
numerical-answers
graph-theory
+
–
4
votes
1
answer
536
Test by Bikram | Mathematics | Test 2 | Question: 3
Read the following statements and identify the correct ones: Any two simple connected graphs with $n$ vertices, where all vertices have degree two, are isomorphic. The maximum vertex connectivity possible is $\lfloor 2e/n \rfloor$. If $G$ is a simple ... . I,II are correct. I,II,III are correct. I,II,IV are correct. I,IV are correct.
Read the following statements and identify the correct ones:Any two simple connected graphs with $n$ vertices, where all vertices have degree two, are isomorphic.The maxi...
Bikram
454
views
Bikram
asked
May 24, 2017
Graph Theory
tbb-mathematics-2
graph-theory
graph-connectivity
+
–
0
votes
1
answer
537
graphtheory,Narsingh Deo,4.26
Suppose a single tennis tournament is arranged among n players and the number of matches planned is a fixed number e (where n-1 < e < n(n-1)/2 ).For sake of fairness,how will you make sure that some players do not group together and isolate an individual (or a group of players).
Suppose a single tennis tournament is arranged among n players and the number of matches planned is a fixed number e (where n-1 < e < n(n-1)/2 ).For sake of fairness,how ...
#Rahul
829
views
#Rahul
asked
May 20, 2017
Graph Theory
narsinghdeo
graph-theory
+
–
0
votes
0
answers
538
#Graphtheory
Construct a graph G with edge connectivity of G =4 ,vertex connectivity of G =3 and degree of every vertex of G >=5
Construct a graph G with edge connectivity of G =4 ,vertex connectivity of G =3 and degree of every vertex of G >=5
#Rahul
663
views
#Rahul
asked
May 20, 2017
Graph Theory
graph-theory
+
–
2
votes
1
answer
539
2 - connected graph
For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$ ... 3 regular and not 2- connected although $d \geq 2$ is satisfied. Why this $d \geq 2$ is trivial and not working in some cases ?
For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$ - connected. (vertex wise).I did in this way :$\begin{alig...
dd
1.3k
views
dd
asked
May 19, 2017
Graph Theory
graph-theory
graph-connectivity
+
–
0
votes
2
answers
540
Isomorphism and subgraph
If there are two graphs G1 and G2 and both are Isomorphic to each other...Is G1 subset of G2?
If there are two graphs G1 and G2 and both are Isomorphic to each other...Is G1 subset of G2?
#Rahul
1.8k
views
#Rahul
asked
May 18, 2017
Graph Theory
graph-theory
+
–
Page:
« prev
1
...
13
14
15
16
17
18
19
20
21
22
23
...
30
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register