Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

2 votes
1 answer
541
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...
User Avatar
0 votes
2 answers
542
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?
User Avatar
0 votes
1 answer
545
nptel exam ada
Total no of edges =1225 Maximum degree of vertex =3 find no of vertices ?
Total no of edges =1225Maximum degree of vertex =3find no of vertices ?
User Avatar
0 votes
0 answers
547
Graph Theory
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
User Avatar
0 votes
1 answer
549
Kenneth Rosen Edition 6th Exercise 8.2 Theorem 1 (Page No. 543)
how to prove that sum of all the vertices in a graph G is equal to twice the number of edges in G. please explain step by step .
how to prove that sum of all the vertices in a graph G is equal to twice the number of edges in G.please explain step by step .
User Avatar
0 votes
1 answer
550
Relation between k and k-1 edge connected graph
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
User Avatar
0 votes
2 answers
551
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y What would be maximum path length between any two vertices of graph ?
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhat would be maximum path length bet...
User Avatar
1 votes
1 answer
552
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Which vertex will have highest in degree ?
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhich vertex will have highest in deg...
User Avatar
3 votes
3 answers
553
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Find number of strongly connected components
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yFind number of strongly connected com...
User Avatar
0 votes
0 answers
555
Self-Doubt
Every Planar graph have vertex cover of size atmost 3n/4. Can someone provide a good link to understand the above fact? Or a good explanation is most welcome.
Every Planar graph have vertex cover of size atmost 3n/4.Can someone provide a good link to understand the above fact?Or a good explanation is most welcome.
User Avatar
3 votes
3 answers
556
graph theory
A graph consists of only one vertex,which is isolated ..Is that graph A) a complete graph ??? B) a clique??? C) connected graph ??? Please explain your answer ...
A graph consists of only one vertex,which is isolated ..Is that graphA) a complete graph ???B) a clique???C) connected graph ???Please explain your answer ...
User Avatar
15 votes
3 answers
557
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
User Avatar
0 votes
2 answers
558
Graph Theory
let G=(V,E) be an connected graph, let $\left | V \right |= n$ Find largest value of n such that i) G is complete & ii) G is bipartite with valid proof
let G=(V,E) be an connected graph, let $\left | V \right |= n$Find largest value of n such thati) G is complete &ii) G is bipartitewith valid proof
User Avatar
0 votes
3 answers
559
Graph Theory Path
What is the difference between path and Euler path?
What is the difference between path and Euler path?
User Avatar
1 votes
3 answers
560
No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such ...
User Avatar
1 votes
4 answers
562
graph theory
chromatic number of a graph <= ( maxdegree of the graph ) + 1 can somebody explain how ?
chromatic number of a graph <= ( maxdegree of the graph ) + 1 can somebody explain how ?
User Avatar
0 votes
2 answers
564
graph theory
State TRUE or FALSE. The chromatic number of a Bi-partite graph is ALWAYS 2.
State TRUE or FALSE.The chromatic number of a Bi-partite graph is ALWAYS 2.
User Avatar
0 votes
1 answer
565
graph theory
The cardinality of the vertex-cut ( seperating set ) of a complete graph with n vertices is ___
The cardinality of the vertex-cut ( seperating set ) of a complete graph with n vertices is ___
User Avatar
0 votes
1 answer
566
graph theory
In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?
In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?
User Avatar
1 votes
2 answers
567
graph theory
The number of independent sets in a complete graph with n vertices is ____
The number of independent sets in a complete graph with n vertices is ____
User Avatar
1 votes
1 answer
568
graph theory
can somebody explain the logic behind this theorem ?
can somebody explain the logic behind this theorem ?
User Avatar
1 votes
2 answers
569
graph theory
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex
User Avatar
1 votes
1 answer
570
graph theory
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex 4) Is {v1,v2,v5} a cut-set ?
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex 4) Is {v1,v2,v5} a cut-set ?
User Avatar
Page: