Repositório Institucional da Universidade de Aveiro > CIDMA - Centro de Investigação e Desenvolvimento em Matemática e Aplicações > CIDMA - Artigos >
 Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/16158

title: Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs
authors: Abreu, N.
Cardoso, Domingos M.
Carvalho, P.
Vinagres, C. T. M.
keywords: Graph spectra
Graph operations
Lexicographic product of graphs
issue date: 6-Jan-2017
publisher: Elsevier
abstract: Consider two graphs G and H. Let H^k[G] be the lexicographic product of H^k and G, where H^k is the lexicographic product of the graph H by itself k times. In this paper, we determine the spectrum of H^k[G]H and H^k when G and H are regular and the Laplacian spectrum of H^k[G] and H^k for G and H arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10^100 ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.
URI: http://hdl.handle.net/10773/16158
ISSN: 0012-365X
publisher version/DOI: http://dx.doi.org/10.1016/j.disc.2016.07.017
source: Discrete Mathematics
appears in collectionsCIDMA - Artigos

files in this item

file description sizeformat
1-s2.0-S0012365X16302382-main.pdfElectronic version945.54 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2