Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by $$ \textrm{lca}(u,v) = \text{the lowest common ancestor of $u$ …

Hi I need the bound for the spectrum gap of random semiregular ($\ell$, $r$)-bipartite graph. This paper (http://arxiv.org/abs/1212.5216) gives the bound for $\ell$-regular bipar …

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 …

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

Let $W$ be a weighted adjacency/affinity matrix for some connected graph. $W$ is symmetric and non-negative. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have high affinity …

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 …

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 …

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 …

$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 …

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, 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 …

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 …

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 …

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 …