Recent questions tagged graph-theory

0 votes

0 answers

1

Kenneth rosen
How many non-isomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$

asked 1 day ago in Graph Theory by swati96 (37 points) | 12 views

0 votes

0 answers

2

Kenneth rosen
How many non-isomorphic graphs are there with six vertices and four edges?

asked 1 day ago in Graph Theory by swati96 (37 points) | 5 views

0 votes

0 answers

3

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

asked 1 day ago in Graph Theory by swati96 (37 points) | 5 views

0 votes

0 answers

4

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

asked 1 day ago in Graph Theory by swati96 (37 points) | 4 views

0 votes

1 answer

5

spanning tree
How we get maximum no. of spanning tree for give $n$ node is $n^{(n-2)}$

asked 1 day ago in Graph Theory by piya (73 points) | 14 views

0 votes

1 answer

6

True/False
Which of the following statements related to graphs are True? Consider a graph with Positive distinct edges 1.If we add a Positive Integer to all edges, then there are chances to get more than one shortest paths between 2 vertices 2.If we add a Positive Integer ... 4.If we add a Negative Integer to all edges, then there are chances to get more than one longest paths between 2 vertices

asked Jun 9 in Graph Theory by Balaji Jegan Active (1k points) | 43 views

0 votes

0 answers

7

[4-14]Connectivity- Narsingh Deo
Show that a simple graph is nonseparable iff for any two given arbitrary edges a circuit can always be found that will include these two edges.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 22 views

0 votes

0 answers

8

[4-13]Connectivity-Narsingh Deo
Show that a graph G is non-separable iff every vertex pair can be placed in some circuit in G.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 11 views

0 votes

2 answers

9

Self-Doubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate2018-18?show=204092#q204092 My doubt is Suppose, I try to colour the vertices of this graph as follows First I colour vertex a and f with colour 1. Then I colour vertex e ... what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours.

asked Jun 7 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 63 views

0 votes

0 answers

10

Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.

asked Jun 6 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 50 views

0 votes

2 answers

11

Number of Subgraphs of Kn?
I was searching for this question and found below link How many subgraphs does $K_5$ have? Here, in general, it is given to be $\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\frac{r(r-1)}{2}}$ My doubt is that the case for $r=0$ is taken if we select none of the vertices of $K_n$? Why the case for $ r=0$ considered?

asked Jun 5 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 38 views

0 votes

2 answers

12

Connectivity(4-20) Narsingh Deo
Is every regular graph of degree d(d$\geq$3) non-separable?If not, give a simple regular graph of degree 3 that is separable.

asked Jun 2 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 60 views

0 votes

0 answers

13

Connectivity(4-10)-Narsingh Deo
Prove that in a connected graph G a vertex v is a cut-vertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x and y.

asked Jun 2 in Graph Theory by Ayush Upadhyaya Loyal (8.7k points) | 36 views

0 votes

0 answers

14

Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15

asked Jun 1 in Graph Theory by Lakshman Patel RJIT Loyal (7.7k points) | 50 views

+2 votes

2 answers

15

Graph Theory
The largest possible number of vertices in a graph $G$, with $35$ edges and all vertices are of degree at least $3$ is $24$ $25$ $23$ $26$

asked May 28 in Graph Theory by Mr khan 3 (121 points) | 100 views

0 votes

3 answers

16

Graph theory | Graph Theory
A simple non directed graph contains $21$ edges, $3$ vertices of degree $4$ and the other vertices are of degree $2$.Then the number of vertices in the graph is? $8$ $13$ $18$ $21$

asked May 28 in Study Resources by Mr khan 3 (121 points) | 41 views

0 votes

1 answer

17

#Algorithms #DFS
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.

asked May 28 in Algorithms by iarnav Loyal (7.2k points) | 38 views

0 votes

1 answer

18

Graph Theory DM
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition- in a path vertices and edges can't repeat so why this is a path. confused please clarify.

asked May 28 in Graph Theory by mbisht (161 points) | 35 views

0 votes

3 answers

19

madeeasy work book
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight in ... weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?

asked May 24 in Algorithms by abhicse (39 points) | 77 views

+1 vote

2 answers

20

Graph Theory #self doubt
Can both euler path and euler circuit exist in same graph. Can both Hamiltonian path and Hamiltonian circuit exist in same graph.

asked May 24 in Graph Theory by Abhinavg (259 points) | 72 views

0 votes

1 answer

21

Clique with one vertex
Is there a clique possible in Graph with one vertex? I mean, is a singleton vertex in itself is a complete sub-graph and can be called a clique.

asked May 18 in Graph Theory by iarnav Loyal (7.2k points) | 96 views

0 votes

0 answers

22

#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?

asked May 13 in Algorithms by iarnav Loyal (7.2k points) | 27 views

0 votes

0 answers

23

TIFR 2018

asked May 5 in Graph Theory by jatinkumar (203 points) | 33 views

0 votes

1 answer

24

Graph Theory & Permutations
Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph? Also, if possible generalise the method for graph with k connected components each having ni vertices. Ans=84

asked May 4 in Graph Theory by Hakuna Matata (317 points) | 74 views

+1 vote

2 answers

25

IISc CDS (MTech-R)
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?

asked May 3 in Graph Theory by Hakuna Matata (317 points) | 89 views

0 votes

2 answers

26

Connected Components
My Doubt is :- 1. If n vertices are there and p are the connected components then total n-p edges will be there. 2. In a simple graph with n vertices and p connected components there are atmost (n-p)(n-p+1)/2 number of edges Now which to ... the answer. Solution of made easy:- (Please tell how did they approached the question and which way is the best way to do such questions)

asked May 2 in Algorithms by Na462 Active (3.3k points) | 154 views

0 votes

1 answer

27

Spanning trees
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?

asked Apr 29 in Algorithms by Durgesh Singh Junior (877 points) | 42 views

0 votes

1 answer

28

Self Doubt
How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?

asked Apr 29 in Algorithms by Durgesh Singh Junior (877 points) | 42 views

0 votes

1 answer

29

Induction
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2 \end{align*}

asked Apr 27 in Graph Theory by Debashish Deka Veteran (56.6k points) | 50 views

0 votes

1 answer

30

Regular polyhedra
Is regular polyhedra in graph theory in our Gate syllabus 2019?

asked Apr 25 in Mathematical Logic by Na462 Active (3.3k points) | 24 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