MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a weighted and directed graph $G$ on $n$ vertices we define the Laplacian matrix by $L(G) = D(G)-A(G)$. Here $(i,j)$-th entry of ${A(G)}$ equals the weight $w_{ij}$ of the edge from $i$ to $j$ if there is one and zero if there is no edge from $i$ to $j$. Furthermore, $D(G)$ is the diagonal matrix, where the $(i,i)$-th entry of $D(G)$ equals $-\sum_{j=1}^{n} w_{ij}$ (after some ordering of the vertex set). We denote the eigenvalues of $L(G)$ by $\lambda_0 = 0, \lambda_1, \ldots$. We assume now that the graph $G$ has only positive edge weights is strongly connected, i.e., from each vertex we can reach every other vertex by using outgoing edges only, then the $\lambda_i$ all have positve real part for $i \neq 0$. We denote by $\lambda_1$ one of the eigenvalues with minimal positive real part (this choice may not be unique).

If we consider the $n$-dimensional hypercube graph $G$ (see for more information), consider each undirected edge as two edges (for both directions between two vertices) and define each edge weight as $1$, we obtain that the laplacian eigenvalues are $2i$ with multiplicity $\binom{n}{i}$ for $i=0,\ldots,n$. Hence, $\lambda_1 = 2$.

My question is now: Is there any $n$ and any labelling with positive weights for the edges of the $n$-dimensional hypercube graph $G$ (considered as directed and weighted graph), where for each vertex the sum over the outgoing respective incoming edge weights equals $n$ and the real part of $\lambda_1$ of $L(G)$ is bigger than 2 (the more the better)? And is there any estimate to these optimally large reals part of $\lambda_1$ as a function of $n$? Of course, it would be good to have a general method to construct such weights, but this would be only optional.

share|cite|improve this question

The graph is symmetric enough that the "standard" weights are almost certainly optimal. For more, check out D. Jacobson and I. Rivin, Extremal metrics on graphs.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.