Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911448573149184 |
|---|---|
| author | Abreu, Nair Cardoso, Domingos M. Carvalho, Paula Vinagre, Cybele T. M. |
| author_facet | Abreu, Nair Cardoso, Domingos M. Carvalho, Paula Vinagre, Cybele T. M. |
| contents | 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]$ 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 finish with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1511_02391 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs Abreu, Nair Cardoso, Domingos M. Carvalho, Paula Vinagre, Cybele T. M. Combinatorics 05C50, 05C76, 15A18 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]$ 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 finish with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers. |
| title | Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs |
| topic | Combinatorics 05C50, 05C76, 15A18 |
| url | https://arxiv.org/abs/1511.02391 |