Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
211 views

Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
2
votes
0answers
34 views

Volume interpretation of number of perfect matchings in bipartite planar graphs

Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...
5
votes
1answer
152 views

“König's theorem” for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...
3
votes
0answers
62 views

Have partition functions of abstract simplicial complexes been examined?

Many complicated probability distributions arising in electrical engineering and machine learning have a simple expression as a sum of products that can also be encoded in a factor graph. The ...
0
votes
0answers
53 views

Hopcroft-Karp Algorithm

I'm studying Hopcroft-Karp algorithm in bipartite graph. I can understand the theorems about the algorithm, but I want to find a more specific example. Can I find a bipartite graph that iterates an ...
1
vote
1answer
95 views

An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...
-1
votes
2answers
69 views

On a condition concerning the number of neighbors in bipartite graphs

For any undirected simple graph $G=(V,E)$ we define for $v\in V$ the set $N(v) = \{w\in V: \{v,w\}\in E\}$. Suppose $A, B$ are finite, disjoint sets, and $G = (A\cup B, E)$ is a bipartite graph with ...
1
vote
0answers
104 views

Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it? Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
0
votes
1answer
77 views

Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
1
vote
1answer
100 views

Algorithm to find a $k$-partite graph

Is there any algorithm which finds any $k$-partite graph of a given graph which is known to be a $k$-partite graph? For example, you are given a graph $G$ with vertices $V$ and edges $E$, and you ...
6
votes
0answers
123 views

Dowker and neighborhood complexes: reference wanted

Let $R$ be a 0-1 matrix whose rows or columns are maximal. Q1. Is there a name for such a matrix (or, e.g., a corresponding relation)? From 0-1 matrix corresponding to an abstract simplicial ...
4
votes
1answer
393 views

Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...
5
votes
3answers
148 views

How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?

To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency ...
2
votes
1answer
90 views

Existence of bipartite subgraphs satisfying degree and edge cardinality constraints

How can we prove the following conjecture? Given any simple unweighted bipartite graph $G(V_1, V_2, E)$, there always exists a subgraph $G'(V_1, V_2, E')$ of $G$ such that the two following ...
0
votes
1answer
48 views

Canonical form for a bipartite graph

I have a bipartite graph, including V1 and V2 vertices, and I would like to convert it to a canonical form. One simple method is converting this graph to a general graph by expanding its adjacency ...
1
vote
2answers
136 views

Hamiltonicity and minimal degree in bipartite graphs

Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that $|A| = |B|$, $\text{...
0
votes
3answers
186 views

Hamiltonian paths in bipartite graphs with 2 sets of “almost” same cardinality

Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ ...
7
votes
1answer
322 views

Graph to Bipartite conversion preserving number of perfect matchings

Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
2
votes
0answers
136 views

Minimal size of the maximum biclique

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each vertex on side $R$ is connected to $k$ vertices on side $...
2
votes
1answer
129 views

Minimal size of the maximal biclique

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, ...
5
votes
0answers
64 views

Moving subsets of bipartite graph

I am dealing with a bipartite graph $G = (L\cup R, E)$. The left and right sets are both assumed to be regular with degrees $d_L$ and $d_R$. Assume $|L| > |R|$ and hence $d_L < d_R$. Let $S \...
3
votes
1answer
103 views

Is bipartite graph genus bound by $O(\mbox{max deg})$?

We know that planar graphs have $O(1)$ degree. We know balanced (each color has same number of vertices) complete bipartite graphs have genus $O(n^2)$. If maximum and average degree are $O(n^\...
6
votes
1answer
63 views

Looking for the name or reference regarding a bipartite graph parameter

I'm writing a paper about a math puzzle and the thing I'm studying ends up equivalent to finding the following parameter of a bipartite graph G with parts X and Y: The largest $k$ such that any $k$ ...
3
votes
2answers
448 views

Applications of Hafnians

I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...
1
vote
0answers
56 views

Cut norm and biclique gap?

Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...
4
votes
0answers
132 views

Maximality with respect to having no marriage

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
-1
votes
1answer
166 views

Marriages in infinite bipartite graphs with many neighbors

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
2
votes
1answer
84 views

Minimum number of edges to add in order to have a biclique cover

Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs? For ...
1
vote
2answers
364 views

Rank Adjacency Matrix Bipartite Graph

I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$). When is the incidence matrix full ...
2
votes
0answers
78 views

Bipartite Defect in Graphs

This question is inspired by a recent related question. Given a bipartition $V=B \cup C$ of the vertices of a graph, call an edge $B$-monochromatic (or $C$-monochromatic) if both ends are in $B$ (or ...
3
votes
0answers
72 views

Finding large bicliques in random bipartite graph

I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
-3
votes
1answer
113 views

Matching in a bipartite graph that saturates all vertices

Let $G=(S,T;E)$ be a bipartite graph without isolated vertices. For every edge $e\in E$, e $=$ $st$ $($ s $\in S$, $ t\in T$) happens the inequality $dG(s)$ $>=$ $dG(t)$. Prove that in $G$ ...
5
votes
1answer
164 views

Number of bipartite graphs with a neighborhood property

Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$ Given two vertices $v_{i,p}$ and $v_{i,q}$, $...
2
votes
2answers
522 views

Maximum number of edges in bipartite graph without cycles of length 4

Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ ...
0
votes
1answer
123 views

Minimum modifications to make a graph bipartite

Let's say I have a graph that is not bipartite. Let's say it is colored red and black and there are some conflicts where two vertices of the same color share an edge. I can introduce a new vertex ...
7
votes
0answers
280 views

Missing count in number of perfect matchings

Let $f(G)$ give number of perfect matchings of a graph $G$. Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$. ...
3
votes
1answer
177 views

What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices. Analogously, what is the ...
3
votes
0answers
102 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
1
vote
1answer
118 views

Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$? I am most interested in $d\leq3$ and $g=0$.
1
vote
0answers
84 views

Expected number of perfect matchings in bounded degree bipartite graphs

Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$. What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
4
votes
3answers
326 views

On number of perfect matchings

Consider $2n$ vertex balanced bipartite graph. If total number of edges is $n^2$ then we have $n!$ perfect matchings. Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite ...
2
votes
0answers
101 views

Regularity for a bipartite graph

Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that: 1) degree of every vertex is not greater then $2^t$ 2) number of all edges is greater than $2^{n +t - O(\log ...
1
vote
0answers
56 views

Largest number of perfect matchings in bounded genus graphs

What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?
3
votes
0answers
70 views

Fraction of graphs with bound on number of perfect matchings

Asymptotically what is the fraction of balanced bipartite graph on $2n$ vertices with at most $cn^{\beta}$ edges having at most $n^\alpha$ perfect matchings for any fixed $c,\alpha>0$ and fixed $\...
1
vote
0answers
183 views

On symmetric difference of $k$-partite perfect matchings

Given a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles. Conversely when is it true that every union of even cycles comes from symmetric ...
2
votes
1answer
140 views

A graph assignment problem

Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $...
2
votes
1answer
273 views

Bipartite dimension of an almost crown graph

A crown graph is a complete bipartite graph from which a perfect matching has been removed. The bipartite dimension of a graph is the minimum number of complete bipartite subgraphs needed to cover ...
6
votes
2answers
302 views

extremal bipartite graph

I'm facing the following question: Given a bipartite graph $G = (L \cup R, E)$. Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$. What is a minimal possible number of ...
7
votes
1answer
407 views

Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...
1
vote
0answers
102 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 $$p_1(t,x)=Det(tI-...