Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

15 votes
4 answers
632
GATE CSE 1988 | Question: 2xvi
Write the adjacency matrix representation of the graph given in below figure.
Write the adjacency matrix representation of the graph given in below figure.
User Avatar
1 votes
1 answer
633
partion of vertex
User Avatar
0 votes
0 answers
634
ME TEst series
What does simultaneous mean here?
What does simultaneous mean here?
User Avatar
0 votes
0 answers
636
Graph theory
proof :- A connected graph any two paths of maximum length share at least one vertex
proof :- A connected graph any two paths of maximum length share at least one vertex
User Avatar
0 votes
1 answer
637
Hamiltonian cycles
Number of distinct Hamiltonian cycles are there in a unlabeled complete graph K6______ [Note : the path a->b->c is same as b->c->a]
Number of distinct Hamiltonian cycles are there in a unlabeled complete graph K6______ [Note : the path a->b->c is same as b->c->a]
User Avatar
1 votes
3 answers
638
Planar graph
The total number of planar graphs can be formed with 5 vertices are _____
The total number of planar graphs can be formed with 5 vertices are _____
User Avatar
0 votes
0 answers
639
Directed graph
How many distinct directed graphs are there nodes labeled 1, 2, 3, 4? [consider graphs with no multiple edges and loops]
How many distinct directed graphs are there nodes labeled 1, 2, 3, 4? [consider graphs with no multiple edges and loops]
User Avatar
0 votes
0 answers
640
graph components
Let G be the graph whose vertex is the set of K-tuples with elements in {0, 1}, with x adjacent to y, if x and y different in exactly two positions. The number of components of G _____ 1 2 3 4
Let G be the graph whose vertex is the set of K-tuples with elements in {0, 1}, with x adjacent to y, if x and y different in exactly two positions. The number of compone...
User Avatar
1 votes
1 answer
641
Algo-coloring
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent node gets same color?
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent nod...
User Avatar
3 votes
2 answers
643
shortest path
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...
User Avatar
1 votes
1 answer
644
Check whether given graph is planar
G1 and G2 are two graphs as shown— (A) Both 01 and G2 are planar graphs (B) Both G1 and G2 are not planar graphs (C) GI is planar and G2 is not planar graph (D) G1 is not planar and G2 is planar graph
G1 and G2 are two graphs as shown—(A) Both 01 and G2 are planar graphs(B) Both G1 and G2 are not planar graphs(C) GI is planar and G2 is not planar graph(D) G1 is not p...
User Avatar
0 votes
1 answer
645
The chromatic number and clique number of C'2k+1(k>3)
The chromatic number and clique number of C'2k+1(k>3) i.e. complement of odd cycle, are respectively ______ 3,2 3,k k,k k+1,k
The chromatic number and clique number of C'2k+1(k>3) i.e. complement of odd cycle, are respectively ______ 3,2 3,k k,k k+1,k
User Avatar
2 votes
1 answer
647
clique number of graph is:
The clique number of graph is _____? can someone also explain what is clique number also?
The clique number of graph is _____?can someone also explain what is clique number also?
User Avatar
2 votes
1 answer
650
Let G be a K-regular bipartite graph with k ≥ 2. Then G has no cut edge
how is this statement correct..can some one give an example?? Let G be a K-regular bipartite graph with k ≥ 2. Then G has no cut edge
how is this statement correct..can some one give an example??Let G be a K-regular bipartite graph with k ≥ 2. Then G has no cut edge
User Avatar
31 votes
4 answers
651
GATE CSE 1989 | Question: 3-vi
Which of the following graphs is/are planar?
Which of the following graphs is/are planar?
User Avatar
3 votes
1 answer
655
Kenneth Rosen Edition 6th Exercise 8.2 Question 43 (Page No. 554)
How many subgraphs possible with at least one vertex for the following two graphs ? (labelled vertices) 1. $K_3$ 2. $W_4$ (total 4 vertices)
How many subgraphs possible with at least one vertex for the following two graphs ? (labelled vertices)1. $K_3$2. $W_4$ (total 4 vertices)
User Avatar
0 votes
2 answers
659
Suppose a connected graph has 15 labeled nodes
Suppose a connected graph has 15 labeled nodes, given that it has an eularian circuit, what is the minimum number of distinct circuits which it must have? [Note : the circuit a->b->c->a is not same as b->c->a->b]
Suppose a connected graph has 15 labeled nodes, given that it has an eularian circuit, what is the minimum number of distinct circuits which it must have? [Note : the cir...
User Avatar
18 votes
1 answer
660
GATE CSE 1990 | Question: 1-viii
A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or ________ modulo $4$.
A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or ________ modulo $4$.
User Avatar
Page: