2
votes
0answers
35 views
How many trees can be constructed from k vertices using an LCA operator?
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$ …
0
votes
0answers
16 views
Spectrum gap of large random weighted semiregular bipartite graph
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 …
2
votes
1answer
87 views
Removing edges from Erdős–Rényi graph to make two nodes disconnected
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 …
4
votes
3answers
153 views
How many Perfect Matchings in a regular bipartite Graph
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
1
vote
0answers
50 views
Upper bound on the difference between two elements of the Fiedler vector (a particular eigenvector of a graph Laplacian)
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 …
0
votes
1answer
109 views
DAG graph and topologic order question
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 …
1
vote
2answers
149 views
Random walk on the hypercube
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 …
4
votes
1answer
89 views
Cayley graphs of finitely generated infinite groups quasi-isometrically embeddable in R^3
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 …
0
votes
0answers
39 views
Proving a lower bound for the maximal eigen-value of a non-negative, irreducible, integer matrix
$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 …
0
votes
0answers
25 views
Bounds on the crossing numbers of de Bruijn graphs and some incidence graphs
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 …
1
vote
0answers
40 views
Fundamental cycle separators and crossing numbers
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 …
1
vote
0answers
23 views
Graphs with vertex-separators of size a function of the diameter…
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 …
0
votes
1answer
235 views
Is there a name for this graph?
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 …
0
votes
0answers
25 views
shortest path in undirected graph in LogSpace
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 …
1
vote
1answer
79 views
Enumerating unlabeled trees with degree at most 3
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 …

