**1**

vote

**1**answer

54 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$.

**4**

votes

**0**answers

164 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$, ...

**3**

votes

**0**answers

59 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 ...

**2**

votes

**0**answers

70 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 ...

**2**

votes

**0**answers

76 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 ...

**2**

votes

**0**answers

131 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 ...

**2**

votes

**0**answers

90 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 ...

**2**

votes

**0**answers

126 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 ...

**2**

votes

**0**answers

178 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

**0**answers

28 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 perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...

**1**

vote

**0**answers

22 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 ...

**1**

vote

**0**answers

91 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

**0**answers

92 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 ...

**1**

vote

**0**answers

103 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 ...

**0**

votes

**0**answers

41 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?

**0**

votes

**0**answers

73 views

### Perfect matchings that never combine to form cycle union cover

Can there be exponential number (in terms of vertices) of perfect matchings on a bipartite graph so that no combination of them yields a union of cycles that cover all vertices?
Is there a way to ...

**0**

votes

**0**answers

55 views

### On symmetric difference of $k$-partite perfect matchings

Suppose we have 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 ...