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
    Commented Feb 28, 2014 at 0:27
  • 1
    $\begingroup$ Cone seems right; suspension should be the corresponding thing with two vertices, shouldn't it? $\endgroup$ Commented 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$ Commented Feb 28, 2014 at 8:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .