The H-join of arbitrary families of graphs
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 by 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]$. During long time 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 were limited to families of regular graphs. In this work, we extend such a determination, as well as the determination of the characteristic polynomial, to families of arbitrary graphs. From the obtained results, the eigenvectors of the adjacency matrix of the $H$-join can also be determined in terms of the adjacency matrices of the components and an associated matrix.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A generalization of Fiedler's lemma and the spectra of H-join of graphsLinear Algebra and its Applications, 2021
- The characteristic polynomial of lexicographic product of graphsLinear Algebra and its Applications, 2017
- Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphsDiscrete Mathematics, 2017
- Spectra of graphs obtained by a generalization of the join graph operationDiscrete Mathematics, 2013
- Some results on graph spectraLinear Algebra and its Applications, 2002
- Main eigenvalues of a graphLinear and Multilinear Algebra, 2001
- A table of connected graphs on six verticesDiscrete Mathematics, 1984
- The walk partition and colorations of a graphLinear Algebra and its Applications, 1982
- Eigenvalues of nonnegative symmetric matricesLinear Algebra and its Applications, 1974
- On the group of the composition of two graphsDuke Mathematical Journal, 1959