Dark Mode

Recent questions tagged bipartite-graph

0 votes

2 answers

1

Bipartite Graph doubt

Çșȇ ʛấẗẻ asked in Graph Theory Aug 29, 2023

by Çșȇ ʛấẗẻ

254 views

1 vote

1 answer

2

Self Made Question
Consider a connected undirected graph G with n vertices, where n > 4. Suppose that G has the property that every vertex has a degree of at least n/2, i.e., deg(v) ≥ n/2 for all vertices v in G. Prove that G must contain a cycle of length at most 3n/4.

LRU asked in Graph Theory Apr 14, 2023

by LRU

326 views

0 votes

1 answer

3

Self Made Question
Let G be a bipartite graph with vertex sets V1 and V2, where |V1| = 12 and |V2| = 18. Suppose that G has a perfect matching, which is a set of edges that covers all vertices in G. What is the minimum number of colors needed to properly color G such that no adjacent vertices share the same color, and how does it relate to the chromatic number of G? Justify your answer.

LRU asked in Graph Theory Apr 14, 2023

by LRU

260 views

1 vote

1 answer

4

Self Made Question
Consider a bipartite graph G with vertex sets V1 and V2, where |V1| = 10 and |V2| = 15. What is the minimum number of colors needed to properly color G such that no adjacent vertices share the same color? Justify your answer and explain how it is related to the chromatic number of G.

LRU asked in Graph Theory Apr 14, 2023

by LRU

203 views

0 votes

0 answers

5

TestBook graph theory questions
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30) A 13 B 17 C n(n−1)2−13×17 D n(n−1)2−2

Sahil_Lather asked in Graph Theory Jan 27, 2023

by Sahil_Lather

502 views

3 votes

0 answers

6

DRDO CSE 2022 Paper 1 | Question: 9
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows. \[\left[\begin{array}{lll} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right]\]

admin asked in Graph Theory Dec 15, 2022

by admin

374 views

0 votes

1 answer

7

Self Doubt - Planarity of Complete Bipartite Graph
How to determine for which m, n the complete bipartite graph $Km,n$ is planar? I am getting two answers from two sources:- A complete bipartite graph $Kmn$ is planar if and only if m<3 or n>3. Source: https://www.javatpoint.com/ ... m ≤ 2 or n ≤ 2. Source: http://www.matthewkahle.org/download/file/fid/573 Need a proper proof of the solution.

Abhrajyoti00 asked in Graph Theory Jul 21, 2022

by Abhrajyoti00

1.1k views

1 vote

3 answers

8

TIFR CSE 2020 | Part B | Question: 11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$

admin asked in Graph Theory Feb 10, 2020

by admin

3.3k views

0 votes

1 answer

9

doubt
what is the diameter and radius of the complete bipartite graph?

Cristine asked in Graph Theory Jan 27, 2019

2.6k views

0 votes

1 answer

10

Gateforum Test Series: Graph Theory - Graph connectivity

Gupta731 asked in Graph Theory Oct 29, 2018

787 views

1 vote

1 answer

11

graph theory
consider a complete bipartite graph K(3,3) The ratio of total number of possible vertex induced subgraphs to the total number of possible edge induced subgraph in given bipartite graph is x:y . then value of x+y is______.

Lone Wolf asked in Graph Theory Sep 23, 2018

1.0k views

1 vote

0 answers

12

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

srestha asked in Graph Theory Sep 21, 2018

1.8k views

1 vote

1 answer

13

doubt
someone post complete solution

Prateek kumar asked in Graph Theory Jan 10, 2018

by Prateek kumar

354 views

2 votes

3 answers

14

breadth first search
The max possible height of BFS tree , if BFS is run on a complete bipartite graph Km,n where m>=1 , n>=1 with starting vertex S is

A_i_$_h asked in Programming in C Sep 17, 2017

2.6k views

0 votes

2 answers

15

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

Tesla! asked in Graph Theory Apr 2, 2017

by Tesla!

808 views

17 votes

2 answers

16

TIFR CSE 2017 | Part B | Question: 13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are ... vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two

go_editor asked in Graph Theory Dec 23, 2016

2.9k views

1 vote

1 answer

17

partion of vertex

iita asked in Graph Theory Dec 16, 2016

by iita

248 views

0 votes

1 answer

18

What is largest no of maximal independent set of complete bipartite graph K(4,2)?
What is largest number of maximal independent set of complete bipartite graph K(4,2)? a)2 b)3 c)4 d)6

neha singh asked in Graph Theory Oct 11, 2016

3.2k views

3 votes

2 answers

19

Question on bipartite graph
The two distinct sets of vertices, which make the graph bipartite are: (A) (v1, v4, v6); (v2, v3, v5, v7, v8) (B) (v1, v7, v8); (v2, v3, v5, v6) (C) (v1, v4, v6, v7); (v2, v3, v5, v8) (D) (v1, v4, v6, v7, v8); (v2, v3, v5)

sh!va asked in Graph Theory Aug 9, 2016

by sh!va

2.1k views

1 vote

1 answer

20

Relation between graphs
Is there is any relation between bipartite graph, complete bipartite and planar graph?

Hira Thakur asked in Graph Theory Nov 21, 2015

478 views

3 votes

2 answers

21

graphs - bipartite
Q) For what value of n Kn can be bipartite a)2 b)3 c)4 d) 5

sumit kumar asked in Graph Theory Apr 14, 2015

2.0k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged bipartite-graph