3
$\begingroup$

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.

This situation has many different names: $G$ is called the cone or the suspension of $H$; the new vertex is called dominating or universal - and probably there are other names that have slipped my mind right now.

My question concerns the difference between the spectral (adjacency) radii of $G$ and $H$. Clearly $\rho(G) > \rho(H)$. Now I vaguely recall seeing somewhere the inequality

$$ \rho(G)-\rho(H) \geq 1. $$

But I am unable to track it down. Is it true? And if yes, is it known?

$\endgroup$
2
  • $\begingroup$ In the case that $H$ is regular, the eigenvalues of $G$ are determined by the eigenvalues of $H$. See mathoverflow.net/questions/75166/… $\endgroup$
    – Tony Huynh
    Feb 28, 2014 at 0:27
  • 1
    $\begingroup$ Cone seems right; suspension should be the corresponding thing with two vertices, shouldn't it? $\endgroup$ Feb 28, 2014 at 5:45

1 Answer 1

5
$\begingroup$

Yes, this is true, but I don't know a reference, so here's a proof (I think). Let $$ R(A, x) = \frac{x^T A x}{x^T x} $$ be the Rayleigh quotient. We know that for a symmetric (in fact Hermitian) matrix $A$ and any vector $x$, $$ R(A, x) \leq \rho(A) $$ with equality if and only if $x$ is the Perron vector for $A$.

Now suppose that $H$ is your original graph, and that $G = H \vee K_1$ is the cone, and that $A(H)$, $A(G)$ are their respective adjacency matrices. Then let $\lambda = \rho(H)$ and suppose that $v$ is a vector such that $A(H) v = \lambda v$, and recall that all the entries of $v$ can be taken to be non-negative. Renumbering if necessary we can assume that $$ A(G) = \left[ \begin{array}{cc} A(H)&j\\ j^T&0 \end{array} \right], $$ where $j$ is the all-ones vector.

Our aim is to exhibit a vector $w$ such that $R(A(G), w) \geq \lambda+1$ thus proving the inequality. So let $w$ be the vector obtained by adjoining an additional coordinate equal to $1$ to $v$. It then follows that $$ A(G) w= \left[ \begin{array}{cc} A(H)&j\\ j^T&0 \end{array} \right] \left[ \begin{array}{c} v\\ 1 \end{array} \right] = \left[ \begin{array}{c} \lambda v + j\\ j^T v \end{array} \right] $$ and $$ w^T w = v^T v + 1. $$ Therefore the Rayleigh quotient $$ R(A(G), w) = \frac{\lambda v^T v + 2 j^T v} { v^T v + 1}. $$

Now assume that $v$ is normalised so that its maximum entry is $1$ and again recall that every entry of $v$ is non-negative. Then we have the inequalities $j^T v \geq v^T v$ (because each $0 \leq v_i \leq 1$) and $j^T v \geq (\lambda +1)$ (because if $i$ is the index such that $v_i = 1$ then $(Av)_i = \lambda$ and $j^T v \geq (Av)_i + v_i$). Putting it all together we have $$ R(A(G), w) \geq \frac{\lambda v^T v + v^T v + (\lambda + 1)}{v^Tv + 1} = \lambda+1. $$

$\endgroup$
1
  • $\begingroup$ P.S. I tried to prove it in the same way bot got stuck because my $v$ was $2$-normalized... $\endgroup$ Feb 28, 2014 at 8:17

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.