Questions tagged [bipartite-graphs]
A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices in the same set are adjacent.
136
questions
0
votes
0
answers
58
views
Can we find a vertex maximal path in a bipartite graph?
Let's define vertex maximal path ($\text{vmp}$): suppose a path $P$ is vertex maximal if its vertex set $V(P)$ and any vertices $v$ can't form a longer path, i.e. the set $V(P)\cup \{v\}$ can't form a ...
1
vote
1
answer
475
views
+100
Covering a connected bounded-degree bipartite graph with connected subgraphs
Let $G = (L,R,E)$ be a finite connected bipartite graph with maximum degree $\Delta\ge2$. A subgraph $H$ is said to be left-neighbourhood closed (LNC for short) if every $v\in L(H)$ satisfies $\...
- 237
3
votes
2
answers
304
views
Algorithm to evaluate "connectedness" of a binary matrix
I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...
- 814
2
votes
1
answer
177
views
Bipartite matching with a pairwise constraint
A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
- 3,959
0
votes
0
answers
65
views
Interpretation of $|V|\,|E|$ for bipartite graphs
Background: the question is motivated by a result in statistical mechanics. I am working with a generalized exclusion process with a fixed number of particles $k$ on a finite graph $G'=(V,E')$, which ...
- 81
4
votes
0
answers
117
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
1
vote
0
answers
81
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 11
2
votes
1
answer
129
views
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$
Suppose a bipartite graph with two parts $A, B$, for every $b \in B$ we know $\deg(b) \ge 1$.
Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$.
- 149
2
votes
0
answers
144
views
Generalizing Hall's marriage theorem to non-perfect matchings
Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
- 121
3
votes
1
answer
228
views
Are "ultra-regular" bipartite graphs complete?
Let $X, Y$ be non-empty, disjoint sets and let $R\subseteq X\times Y$ be a binary relation. For $x\in X$, we set $R(x) = \{y\in Y: (x,y) \in R\}$ and for $y\in Y$, let $R^{-1}(y) = \{x\in X:(x,y)\in R\...
1
vote
0
answers
41
views
Tightness of the bounding the operator norm of graph by average degree from below
Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue
$\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
- 391
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
2
votes
2
answers
97
views
Real-world datasets for testing the maximum edge bi-clique problem
We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
- 23
3
votes
0
answers
98
views
Number of planar bipartite graphs
How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?
- 13.8k
2
votes
0
answers
175
views
Ramanujan graphs in Polynomial time
I am a research scholar with a computer science background, currently working on graph theory. I am working on a reduction to prove that a problem is NP-complete. I need to include the Ramanujan graph ...
