The H-join of arbitrary families of graphs -- the universal adjacency spectrum

DOI10.1016/J.LAA.2022.04.015zbMATH Open1490.05236arXiv2101.08383OpenAlexW4225266818MaRDI QIDQ2144241FDOQ2144241

Authors: Helena Gomes, Sofia J. Pinheiro, D. M. Cardoso 

Publication date: 1 June 2022

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The $H$-join of a family of graphs $mathcalG=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 $mathcalG$ 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 $mathcalG$ 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.

Full work available at URL: https://arxiv.org/abs/2101.08383

Recommendations

• A generalization of Fiedler's lemma and the spectra of \(H\)-join of graphs
• Spectra of graphs obtained by a generalization of the join graph operation
• The spectra of signed graphs obtained by \(\dot{H}\)-(generalized) join operation
• Signless Laplacian and normalized Laplacian on the \(H\)-join operation of graphs
• Eigenvalues of a \(H\)-generalized join graph operation constrained by vertex subsets

zbMATH Keywords

graph operationsgraph eigenvaluesuniversal adjacency matrixwalk-matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• The walk partition and colorations of a graph
• Some results on graph spectra
• The main eigenvalues of a graph: a survey
• Eigenvalues of nonnegative symmetric matrices
• Handbook of product graphs
• The composition of graphs
• A table of connected graphs on six vertices
• Title not available (Why is that?)
• On the group of the composition of two graphs
• Spectra of graphs obtained by a generalization of the join graph operation
• Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The spectral approach to determining the number of walks in a graph
• Main eigenvalues of a graph
• Lexicographic polynomials of graphs and their spectra
• The characteristic polynomial of lexicographic product of graphs
• Main eigenvalues of real symmetric matrices with application to signed graphs
• A generalization of Fiedler's lemma and the spectra of \(H\)-join of graphs
• On the spectral characterization of mixed extensions of \(P_3\)

Cited In (7)

• Eigenvalues of a \(H\)-generalized join graph operation constrained by vertex subsets
• A generalization of Fiedler's lemma and the spectra of \(H\)-join of graphs
• Universal spectra of the disjoint union of regular graphs
• Title not available (Why is that?)
• The spectra of signed graphs obtained by \(\dot{H}\)-(generalized) join operation
• The complete classification of graphs whose second largest eigenvalue of the eccentricity matrix is less than 1
• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

This page was built for publication: The \(H\)-join of arbitrary families of graphs -- the universal adjacency spectrum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144241)