# A graph eigenvalue problem

This is motivated by a graph problem considered by me. For a directed graph $G$ on nodes ${1,\cdots,N}$, denote its graph Laplacian by $L$($l_{ij}=-1$ iff there is an directed edge $j\rightarrow i$ and zero otherwise, and $l_{ii}=-\sum_{k\neq i}l_{ik}$). For a graph $\bar G$ on the node set ${0, 1, \cdots, N}$, define $H=L+D$, where $L$ is the Laplacian matrix of the subgraph $G$ on ${1,\cdots,N}$ and $D=diag(d_1, \cdots, d_N)$ with $d_i=1$ if $0\rightarrow i$, and with $d_i=0$ otherwise. We assume there is no eldge of the form $i \rightarrow 0$ in graph $\bar G$.

It can be shown that $Re\lambda_{min}(H)\geq 0$, and furthermore, if there is a path from node 0 to any other node $i$ in graph $\bar G$, them $Re\lambda_{min}(H)>0$. The result can be extended as follows:

If there is a path from node 0 to any other node $i$ in graph $\bar G_1$ $\cup$ $\bar G_2$ $\cup$ $\bar G_3$, then $Re\lambda_{min}(H_1+H_2+H3)>0$ or $Re\lambda_{min}(\tau_1 H_1+\tau_2 H_2+\tau_3 H_3)>0$ for any $\tau_i>0, \tau_1+\tau_2+\tau_3=1$.

Define the set $\Gamma=[(\tau_1,\tau_2,\tau_3)|\tau_1+\tau_2+\tau_3=1, \tau_i \geq \tau, i=1,2,3]$,where $\tau \in (0,1)$ is a given number. Colsely related to what i am considering is the question that whether or not the inequality $inf_{(\tau_1,\tau_2,\tau_3)\in \Gamma}Re\lambda_{min}(\tau_1 \mathcal{H}_1+\tau_2 \mathcal{H}_2+\tau_3 \mathcal{H}_3)>0$ hold?

Thanks.

-
What are $G_{1},G_{2},G_{3}$? I lost you there. – Felix Goldberg May 10 '12 at 12:24
Here, $\bar G_1, \bar G_2$ and $\bar G_3$ are three graphs defined on the node 0,1,\cdots N. The individual graph may not connected, but the union graph $\bar G_1 \cup \bar G_2 \cup \bar G_3$ has a spanning tree. Your mentioned $G_i$ is a subgraph of $\bar G_i$ and it is defined on the nodes $1, \cdots,N$. Thanks for your attention. – W. Nyway May 11 '12 at 0:48