Questions tagged [bipartite-graphs]
For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.
705
questions
-3
votes
0
answers
35
views
Prove: For any simple, connected, planar graph $G$, $e\le 3v-6$
Prove: For any simple, connected, planar graph $G$, $e\le 3v-6$
Let $G$ be a planar, simple, connected graph. $G$ is isomorphic to itself and thus, by the property of invariance, is also bipartite. By ...
0
votes
1
answer
73
views
Maximal spectral norm of balanced $\pm 1$ matrix [closed]
Suppose that we have a square matrix $A = [a_{ij}] \in {\Bbb R}^{n \times n}$ whose entries are $\pm 1$ and whose columns are balanced, i.e., $\sum_{i=1}^n a_{ij}=0$. How large can the spectral norm ...
- 351
0
votes
0
answers
26
views
Non-complete bipartite graph notation
How to denote a non-complete bipartite graphs? Because as far as I know, $K_{m, n}$ notation is only for complete bipartite graphs.
3
votes
1
answer
63
views
Non-isomorphic bipartite Graphs with same degree sequence and cycles
I am still trying to understand the graph isomorphism problem for bipartite graphs. I know two bipartite graphs cannot be isomorphic if they do not possess the same degree sequence or not the same ...
- 31
0
votes
0
answers
26
views
Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the maximum degree of G.
Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the
maximum degree of G. Using Halls Theorem. I need a good proof, I am studying for an exam and I need to understand ...
0
votes
0
answers
24
views
How to prove the existence of groups for bipartite graph?
I have a simple bipartite graph with bipartition (W, C) such that $|W| < |C|$, each vertex $c \in C$ has 2 edges (so to two different vertices w each time) and each vertex $w \in W$ has 4 edges. I ...
- 1
0
votes
1
answer
44
views
Bipartiteness of hypercube graph with at least one edge contracted
I am participating in a research in my university and as a side task I need to solve the following problem:
Consider a hypercube graph. Someone contracts one edge in it.
What is the minimum number of ...
2
votes
1
answer
34
views
Proving possibilities of building bipartite 2 colored graphs with n vertices
I want to show that I can you can build a two-colorable graph for all n that have n vertices and $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges. After this, I want to show that it is impossible to ...
- 43
2
votes
1
answer
57
views
At least n lines to cover all ones when each row and column has exactly k ones
Given is an $n{\times}n$ $(0, 1)$ matrix $A$. Prove that if
in each row and in each column there are exactly $k$ ones, where $k\ge 1$, then it is impossible to cover all $1$s in the matrix using less ...
- 91
0
votes
2
answers
83
views
Prove bipartite graphs have a perfect matching of $X$ into $Y$ if $\deg(x)\ge \deg(y)$ for all $x\in X$ and $y\in Y$
I have an exercise from here involving Hall's Theorem:
Let G be a bipartite graph on the parts $X$ and $Y$, and
suppose that the inequality $\deg(x)\ge \deg(y)\ge 1$ holds for all $x\in X$ and $y\in ...
0
votes
0
answers
34
views
Let $n\geq 3$. Is there a connected, planar, bipartite graph with $n$ regions and $n$ vertices?
The answer given is that according to a Corollary of Euler’s formula (Corollary 3 Section 10.7), such a graph has at most $2n − 4$ edges. Applying this to Euler’s formula ($r = m − n + 2$), there are ...
- 1
4
votes
1
answer
74
views
Friendship theorem for bipartite graphs
The friendship theorem states that if every pair of people has exactly one common friend, then one person is friends with everybody. Which is unfortunately not easy to actually proof. I came up with ...
- 208
0
votes
1
answer
34
views
Every bipartite graph is an induced subgraph of a hypercube graph?
UPDATE: THIS IS FALSE.
I came up with this question some day and have been working on it for some time:
Every bipartite graph $G$ is an induced subgraph of a hypercube graph $Q_n$.
Here the ...
- 460
2
votes
1
answer
59
views
Derive the number of all labelled, balanced, 2-regular bipartite graphs [duplicate]
I'm trying to explicitly derive the number $B_{2,k}$ of all labelled bipartite graphs with $k$ left nodes, $k$ right nodes, and every node has degree $2$. (these are labelled, balanced, 2-regular ...
- 2,404
1
vote
1
answer
57
views
Criteria for infeasibility of bipartite graph full matching/linear sum assignment
I am trying to (programmatically) find a minimum weight matching in a large bipartite graph (over a thousand nodes on both sides with over a million edges), and I run into an issue where the "...
- 55
2
votes
1
answer
168
views
Find the minimum vertex cover for a Bipartite Graph, if we are given the maximum Bipartite Matching [duplicate]
From Konig's Theorem, the size of Maximum Matching (|M|) and minimum vertex cover is the same. Now we can include both ends of the matching in the vertex cover to find a vertex cover, but its size ...
3
votes
1
answer
86
views
Question about König's Theorem for bipartite graphs
Does König's Theorem imply that the independence number of a bipartite graph is equal to the minimum number of cliques that cover all vertices?
König's Theorem states that the size of a maximum ...
- 335
0
votes
0
answers
50
views
Independence Number and Shannon Capacity of Bipartite Graph
Let $\alpha(G)$ denote the independence number of $G$ and $S(G)$ the Shannon capacity. Show that for every bipartite graph $G$, $\alpha(G)=S(G)$.
This seems to be true, but I'm not sure how to proceed ...
- 335
4
votes
1
answer
79
views
Graph with large minimum degree can be union of few complete (bipartite) graphs
Problem:
Let $G$ be a bipartite graph with $n$ vertices on each side and
minimum degree $n-d$. Show that it can be written as the union of
$O(d\log n)$ complete bipartite graphs.
My approach with ...
- 647
0
votes
0
answers
49
views
Hungarian Algorithm for minimal cost
I'm trying to learn how the cost minimising Hungarian Algorithm works on bipartite graphs. I can perform the algorithm on the adjacency matrix, but I want to understand how it works on graphs. I ...
- 143
0
votes
0
answers
39
views
Providing a certificate for maximum cardinal matching
I have bipartite graph with six nodes on each side. I have found one of the maximum cardinal matches with 4 pairs.
How do I provide a certificate (which can be checked with O(|V | + |E|) elementary ...
- 125
0
votes
1
answer
57
views
Using minimum cover to find maximum matching in bipartite
I was shown an algorithm in a test for using minimum vertex coverage in bipartite graph to find maximum edge matching. It made a lot of sense to me and I failed to come up with an example that proves ...
- 33
4
votes
1
answer
119
views
Bipartite graph "matching" with multiple edges per node
I'll preface by saying that I know that the title is technically incorrect since a matching is defined such that each node has at most one edge. However I can't find the correct term so here I am
I ...
- 55
3
votes
1
answer
71
views
"One-Sided Hungarian" or "Hungarian for Roommate Problem"
The Hungarian algorithm is a solution to a two-sided matching problem. There are similar "one-sided" matching problems, such as the roommates problem. Like the Hungarian, roommates need to ...
- 260
4
votes
1
answer
74
views
How to count pairs with Catalan distribution
Say I have a set of $n$ pairs, such that I have a total of $2n$ elements. I arrange them in pairs following a Catalan distribution, i.e. if I lay them in a 1D line, I have no crossing (See the ...
- 99
7
votes
1
answer
84
views
Multidimensional Assignment: Is it really NP-Hard? Why? What's the Intuition?
I recently learned about the multidimensional version of the assignment problem (the 1:1
version was studied in the Kuhn-Murkes Hungarian algorithm for bipartite graphs).
The article I was reading was ...
- 260
0
votes
2
answers
34
views
Hungarian Extension: Additive Costs, Non-Additive Benefits
I have a problem that's adjacent to the Hungarian algorithm, but not identical. Suppose I have $N$ workers and $N$ jobs, and I want to develop a matching for all $N$ on both sides. There are $N!$ ways ...
- 260
1
vote
1
answer
83
views
Face, dimension, inequality of a polyhedron
I have a polyhedron:
$$\begin{align}
P = \{x \in R^3 \;\mid\;& x_1 + 2x_2 \ge 4 \tag1 \\
&2x_1 − x_2 \ge 3 \tag2 \\
&x_2 \ge 1 \tag3 \\
&x_1 + x_3 \ge 4 \tag4 \\
&2x_1 + 2x_2 − x_3 ...
user1127565
1
vote
1
answer
60
views
Bipartite Capacity Graph Theory Proof
$ G = (V,E) $ is a bipartite graph and $ V = V1 ∪ V2 $.
$ U ⊆ V1 $ and is denoted as $ N(U) $ and is the set of all neighbours of $U$ in the graph $G$.
Construct an ordered graph $D = (V’,A)$ of G and ...
- 101
1
vote
1
answer
84
views
Given an undirected (potentially disconnected) Graph G = (V, E), is G bipartite? In O(|V| + |E|)
Telling whether a given connected graph is bipartite/2-colorable in O(|V| + |E|) is relatively simple with a BFS approach. This however will not work with disconnected graphs since other subgraphs may ...
- 13
0
votes
1
answer
55
views
The average degree in a bipartite graph
I was solving the following problem from "A First Course in Network Science" by Menczer, Fortunato & Davis.
(p110, Problem 1.25)
Netflix keeps data on customer preferences using a big ...
- 1,327
0
votes
0
answers
28
views
sums of products
Consider the set $M(n) = \{ xy : 0\le x,y \le n\}$.
It was shown by Ford that for $n \to \infty$ we have $|M(n)| \in \Theta\left(\frac{n^2}{(\log n)^\delta(\log\log n)^{3/2}}\right)$, in particular, $|...
1
vote
1
answer
328
views
Let $G = (V, E)$ be a forest, prove that there always exists a function $f:V\to \{0, 1\}$ such that $(u, v)\in E$ so $f(u)\neq f(v)$
I have been looking everywhere for answers but I do not understand how can there be a function that takes a vector from a graph and returns a $0$ or $1$ and some how it won't repeat itself.
Can you ...
0
votes
0
answers
40
views
Is there a way to construct a bipartite $c$-expander graph, for a given $c >0$?
Suppose that $c > 0$ is a real number. Suppose that we are given integers $n > 0$ and $m > 0$. There are many bipartite graphs $G = (L, R, E)$ with $|L| = |R| = n$ vertices on each side and $|...
- 1
1
vote
1
answer
62
views
How to count pairs between odd-even number given a partition between sets
I am trying to solve a combinatorics problem which I do not know how to generalize. Let's say we have two sets of $n$ elements. We label set 1 with odd numbers and set 2 with even numbers.
For example,...
- 99
0
votes
0
answers
106
views
What is a non-bipartite matching problem and what are some of the real life applications of non-bipartite matching?
I know what bipartite matching is. In bipartite matching, we look for a one-to-one match between two disjoint sets of vertices. A classic real-life example of bipartite matching is matching kidneys. I ...
- 87
2
votes
1
answer
99
views
Bipartite graph: Average number of cuts for a given partition
Say I have a graph with an even number of nodes. We then randomly connect those nodes. The possible number of combinations boils down to $P=\frac{(2n)!}{2^n n!}$. We now make a partition of length $L$ ...
- 99
1
vote
0
answers
29
views
Connected dominating set in bipartite graphs.
Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.
Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:
$\Theta(1)<n_b<...
- 211
0
votes
0
answers
20
views
Number of Vertices in a Box/Cartesian Product between Two Complete Bipartite Graph
One of my assignments needs me to create the box product between $K_{{2},{3}}$ and $K_{{1},{3}}$. After creating my own graph using standard methods. I was able to create a graph with 20 vertices ...
- 21
1
vote
1
answer
55
views
Prove that every graph is a minor of a bipartite graph.
I am stuck on this problem and need help figuring it out.
Here are some of my thoughts:
A bipartite graph contains no odd cycle.
Every n odd cycle is a minor of n+1 even cycle.
- 23
1
vote
1
answer
182
views
Is a maximal planar bipartite graph containing cut vertices isomorphic to a star?
A simple graph $G$ is called maximal planar bipartite if it has the property: if we add an
edge (without adding vertices) to $G$, we obtain a graph which is no longer planar, bipartite or simple.
See ...
- 1,566
1
vote
1
answer
99
views
Decomposition of a bipartite graph $G$ into $k$ edge-disjoint spanning subgraphs.
$\textbf{Question:}$ Let G be any bipartite graph and suppose that $k\geqslant 1$. Then $G$ is the union of $k$ edge disjoint spanning subgraphs $G_1 , G_2, \ldots, G_k$ such that $$\left\lfloor\frac{...
- 267
2
votes
1
answer
123
views
"Complete" Labelling of Complete Bipartite Graphs
Consider the complete bipartite graph $K_{n,n}$ on $2n$ vertices (e.g. there are vertices $v_1,\dots,v_{2n}$ with an edge between $v_i$ and $v_j$ iff $i\not\equiv j \pmod{2}$).
A complete labelling is ...
4
votes
1
answer
77
views
Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$
Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$, the
number of shortest paths from $A$ to $B$ is odd. Prove that $G$ is a tree.
Suppose $G$ is a bipartite planar ...
- 197
0
votes
1
answer
39
views
Connected Bipartite Vertex-transitive Graph Recognition
For vertex-transitive graphs, the computational complexity of recognizing them is still unknown. So here comes the question: if it is guaranteed that the input graph is bipartite and connected, is ...
- 83
0
votes
1
answer
56
views
Decompose large bipartite graph into small bipartite graphs?
Given a bipartite graph $G$ with parts $A_i$ and $B_i$ with maximum degree $d$.
We may assume that $|U|,|V|\le n$ and $n\ge d$.
I am wondering is it possible to decompose $G$ into vertex-disjoint ...
- 1,779
3
votes
2
answers
213
views
Matching in a bipartite graph with classes $A$ and $B$ and $d(a) \geq 1$ for all $a \in A$. And $d(a) \geq d(b)$ for all $(a,b) \in E(H)$
Let $H$ be a bipartite graph with classes $A$ and $B$. Further we have that $d(a) \geq 1$ for all $a \in A$. And $d(a) \geq d(b)$ for all $(a,b) \in E(H)$.
I want to show that $H$ contains a matching ...
- 119
1
vote
1
answer
107
views
Prove A can be written as the sum of such matrices
Let $A$ be a matrix whose entries are either 1 or 0.The number of entries which equals 1 for every row of $A$ is exactly $k$ and the number of 1 for every column is no larger than $k$.Prove that there ...
- 693
1
vote
1
answer
133
views
Finding the longest cycle in a bipartite graph?
Given an undirected unweighted and unbalanced bipartite graph, I am looking for an algorithm (and maybe an implementation?), to find (approximately?) longest simple cycles. In my problem each part ...
- 121
1
vote
1
answer
57
views
Vertices connection of Assignment Problem in Bipartite Graph
I'm doing a C++ project that requires solving the Assignment Problems.
During the study of the subject I have a doubt, is it possible that in any assignment problem, one or more arcs that connect any ...
- 13