The H-join of arbitrary families of graphs
Authors:
- Domingos M. CardosoDCDomingos M. Cardoso
- Helena GomesHGHelena Gomes
- Sofia J. PinheiroSPSofia J. Pinheiro
Preprint
Abstract
The $H$-join of a family of graphs $\mathcal{G}=\{G_1, \dots, G_p\}$, also called the generalized composition, $H[G_1, \dots, G_p]$, where all graphs are undirected, simple and finite, is the graph obtained from the graph $H$ replacing each vertex $i$ of $H$ by $G_i$ and adding to the edges of all graphs in $\mathcal{G}$ the edges of the join $G_i \vee G_j$, for every edge $ij$ of $H$. Some well known graph operations are particular cases of the $H$-join of a family of graphs $\mathcal{G}$ as it is the case of the lexicographic product (also called composition) of two graphs $H$ and $G$, $H[G]$, which coincides with the $H$-join of family of graphs $\mathcal{G}$ where all the graphs in $\mathcal{G}$ are isomorphic to a fixed graph $G$. So far, the known expressions for the determination of the entire spectrum of the $H$-join in terms of the spectra of its components and an associated matrix are limited to families of regular graphs. In this paper, we extend such a determination to families of arbitrary graphs.