1

I am wondering the following. If we add a pendant vertex to a graph we are changing the spectrum. Eigenvalue interlacing tells us that the largest e-value of the new graph is at least as big as that of the old, and the smallest is at least as small, but what I'm wondering is whether they can both be equal. I feel somehow that either the largest should be strictly larger or the smallest should be strictly smaller, or both. I'm particularly interested in the bipartite case, because in that case both spectra are symmetric, so if the largest e-value is strictly larger than the smallest must be strictly smaller. Does anyone know about this? My guess could also be wrong, but I don't see how to prove it or find a counterexample.

Thanks, Greg

user387394
  • 594
  • Perron-Frobenius gives a strict increase, if you start with a connected graph. – Chris Godsil Sep 11 '21 at 01:16
  • Thanks for your answer, and please forgive me for being dense, but how does P-F give a strict increase? I'm thinking that P-F here just tells us that the largest positive eigenvalue is a simple one, and it's the largest in absolute value. But no doubt I'm missing something. And yes, I'm only interested in the connected case. – user387394 Sep 11 '21 at 10:24
  • Markovsky: fair comment, but the Perron-Frobenius theorem has a number of parts. See, e.g., the wikipedia page. It tells us that the spectral radius of a proper subgraph of a connected graph is less than the spectral radius of the graph – Chris Godsil Sep 11 '21 at 15:02
  • Ah, I see what you mean. So the fact that we're adding a pendant vertex isn't important, rather what we need is just that the bigger graph is connected. I guess I need to understand P-F better. Thank you! – user387394 Sep 12 '21 at 20:45

0 Answers0