Hi Guys, We have a d-regular bipartite Graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. i want to know a Upper Bound of the number of Matching Thankx

Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result tha …

I'm given $W$---a weighted adjacency/affinity matrix for some connected graph. Then $L = \mathrm{diag}(W\mathbf{1})-W$ is the (unnormalized) graph Laplacian. Let $v$ be the Fiedle …

I need to find the maximum number of topological sorts on Direct Acyclic Graph of N-order. I've checked by running Depth first search algorithm on various Direct Acyclic graphs, an …

Hi there, My question today is related to bounds for the crossing number $cr$ of the $k$-dimensional de Bruijn graph $B(t,k)$ on $t$ symbols (http://en.wikipedia.org/wiki/De_Bruij …

Hi there, I have a question somehow related to a previous question of mine http://mathoverflow.net/questions/131157/fundamental-cycle-separators-and-crossing-numbers. Consider a …

$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eig …

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number …

Hi there, Consider a planar graph $G$ of radius $r$ and order $n$. Lipton and Tarjan proved that $G$ contains a cycle $C$ of length at most $2r+1$ whose removal leaves two connect …

Dear friends, I am only a theoretical physicist. However, the answer to this question is relevant for emergence of space-time from a quantum cellular automaton (in the future I wi …

Given an undirected graph G (can be cyclic) with the promise that all its faces have 3 sides is it possible to find the minimum distace between a source and any other vertices in L …

Does anyone know if there is currently any research or any potential bounds on the number of trees on $n$ vertices with degree at most $3$? One can bound this above by $C_{n}$ the …

I'm trying to find out whether the following graph has a name: Let $W$ be an $n$-dimensional vector space over $GF(q)$. The vertices of the graph are all the subspaces of $W$. Two …

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled …

Consider a connected graph $G$ with min-cut $c$. Suppose the edges fail (are removed) independently with probability $p$. Then $U(p)$, the probability that $G$ becomes disconnected …