1
$\begingroup$

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 http://en.wikipedia.org/wiki/Hypercube_graph 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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