Изменение спектра графа

[A.M.V.]

Нужна идея. Есть граф G1 и G2. Произвели склеивание графов по вершине х. Как при этом изменится спектр графа?

[Утундрий]

A.M.V. в сообщении #1669203 писал(а):

Как при этом изменится спектр графа?

Он не изменится, он возникнет.

[A.M.V.]

Точнее какой возникнет спектр и как он будет связан со спектрами G1 и G2.

[Утундрий]

Максимально непредсказуемым образом, в зависимости от того, скольким вершинам была инцидента (в обоих графах) та самая $x$. Вообще, вопрос напоминает мне анекдот про полметра колючей проволоки.

[Евгений Машеров]

Спектры исходных графов и объединённого непосредственно сопоставлять сложно, поскольку даже размерности их разные. Как вариант - рассмотреть несвязный граф, полученный объединением двух графов и ввести соединяющее вершину одного с вершиной другого ребро.
Оценки для с.з. такого графа можно поискать у Парлетт, "Симметричная проблема собственных значений", п. 10.6

[A.M.V.]

G1, G2 известны и их спектры - тоже. Берем вершину x G1и y G2, производим склеивание по ним. Находим спектр полученного графа.