1
$\begingroup$

I'm trying to prove that if a matrix $G$ is edge transitive, we can say that

$$\vartheta(G) = \frac{n\lambda_{min}(A_G)}{\lambda_{max}(A_G) -\lambda_{min}(A_G)}$$

Where $\vartheta(G)$ is defined in multiple ways:

  • $\min\{ t \mid C-J\succeq 0$ , $C_{ii} = t$ $\forall i\in V$, $C_{ij}=0$ for $\{i,j\}\in \bar{E}\}$ (With $J$ matrix of all ones)
  • $\max\{ \Sigma_{i\in V} Y_{ii} \mid Y\succeq 0$, $Y_{00} =1, Y_{ij}=0$ for $\{i,j\}\in E$, $Y_{0i}=Y_{ii}\}$

I have already shown for $k$-regular graphs $G$ that $$\vartheta(G) \leq min_{x\in\mathbb{R}} \lambda_{max}(J-xA_G) $$

So, i'm thinking the answer should be somewhere in the adjacency matrix.

Any wisdom that can help me get this show on a road?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.