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.
1
vote
0answers
79 views
Curve associated to bipartite graph
Given real biadjacency matrix $A\in\{0,1\}^{n\times n}$ of a bipartite graph with rank $r\in[2,n-1]$, denote $A(x)$ to be matrix where $0$ is replaced by $x$ and $1$ by $1-x$. Denote ...
1
vote
2answers
177 views
Expected matching in a bipartite graph
Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
2
votes
1answer
274 views
Solving assignment problem using Hungarian method vs min cost max flow problem
The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...
3
votes
1answer
205 views
Polygamous stable marriage/ assignment problem
I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
2
votes
0answers
77 views
Minimum number of perfect matchings in a regular bipartite graph
Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?
One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
-4
votes
1answer
164 views
Bipartite graph [closed]
First of all, thank you for your time to reading my post.
I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just ...
2
votes
0answers
75 views
Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices
Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...
1
vote
1answer
132 views
Sequences that represent different drawing of chords?
In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually my question is ...
6
votes
1answer
148 views
Does high min degree and high odd girth imply near bipartiteness?
Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
2
votes
0answers
113 views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of ...
1
vote
2answers
414 views
Enumeration of labeled connected bipartite graphs given partite sets
What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?
1
vote
0answers
73 views
Details about Kelman's equivalent form of Barnette's conjecture
Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
2
votes
1answer
331 views
bipartite graph coloring
Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...
0
votes
1answer
250 views
Counting matchings in a bipartite matching-covered graph
A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & ...
2
votes
1answer
128 views
Searching for equal subsets in a bipartite graph
Let $(U,V)$ be a finite bipartite graph of two parts $U$ and $V$. For any subset $u\subset U$ define the image $Im(u)$ in $V$ consisting of all vertices of $V$ connected to at least one vertex of $u$.
...
0
votes
1answer
194 views
Good lower bound on matching in bipartite graph
Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...
4
votes
2answers
156 views
Bipartiteness criterion
A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that ...
2
votes
0answers
152 views
Structure of almost all bipartite graphs
I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true ...
1
vote
2answers
380 views
Similarity measure between 2 bi-partite graph.
Hello there, i need to solve this problem:
I have 2 different bi-partite weighted graph, g1 and g2 and i would like to measure their similarity, g1 and g2 may have different number of vertex and edges ...
1
vote
0answers
92 views
How many extreme maximal cliques are in an n*m 0-1 matrix?
We can use an n*m 0-1 matrix to denote a bipartite graph. Mining maximal bicliques in such matrix is an open problem.
The extreme maximal clique is a special maximal clique. A clique in such matrix ...
8
votes
1answer
347 views
When does a `distinguished matching' exist?
Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$.
Definition: A distinguished matching is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that:
For all $y\in Y$, ...
2
votes
2answers
233 views
Finding maximal k-degenerate subgraphs
Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$?
I've ...
4
votes
0answers
148 views
Bounds on numbers of matchings of given sizes in bipartite graphs
I am interested in the following question:
For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
9
votes
2answers
488 views
Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?
Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
2
votes
1answer
229 views
Bipartite graphs with prescribed Matching $M$ and genus $g$.
Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color.
Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings.
My first ...
2
votes
1answer
315 views
Obstructions to genus $g+1$ bipartite graph having genus $g$
Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices.
Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...
6
votes
2answers
740 views
Condition on a bipartite graph to have an $m$-factor
This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.
Let $G$ be a bipartite graph, i. e., a graph ...
