Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be 2 graphs:

Union of 2 graphs $G_1 \cup G_2=(V_1 \cup V_2,E_1 \cup E_2)$;

Composition of 2 graphs $G_1[G_2]$;

Sum(join) of 2 graphs by $G_1+G_2=(V(G_1)\cup V(G_2),E(G_1) \cup E(G_2) \cup \{\{ u_1,u_2\}|u_1\in V(G_1),u_2 \in V(G_2)\}).$

What can be said about spectrum of $G_1\cup G_2$, $G_1[G_2]$ and $G_1+ G_2$ and replacement and zig-zag product related to $spec(G_1)$ and $spec(G_2)$ ?


closed as unclear what you're asking by Wolfgang, Chris Godsil, Jan-Christoph Schlage-Puchta, András Bátkai, Andrej Bauer Aug 16 '16 at 13:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ See section 2 (in particular section 2.5) of Cvetkovic, Doob & Sachs, Spectra of graphs. [I only have an old edition, but hopefully this did not change.] They deal with a lot of these as special cases of "NEPS". See also section 2.1 of Cvetkovic, Rowlinson & Simic, An introduction to the theory of graph spectra, 2010. For the zig-zag product, I only know of the spectral gap preservation (see the paper by Reingold, Vadhan et Wigderson from 2002) but there might have been other things published since. $\endgroup$ – ARG Aug 3 '16 at 5:20