Lexicographic products and lexicographic powers of graphs -- a walk matrix approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911006397038592 |
|---|---|
| author | Cardoso, Domingos M. Carvalho, Paula Gomes, Helena Pinheiro, Sofia J. Rama, Paula |
| author_facet | Cardoso, Domingos M. Carvalho, Paula Gomes, Helena Pinheiro, Sofia J. Rama, Paula |
| contents | The characteristic polynomial and the spectrum of the lexicographic product of graphs $H[G]$, a specific instance of the generalized composition (also called $H$-join), are explicitly determined for arbitrary graphs $H$ and $G$, in terms of the eigenvalues of $G$ and an $H[G]$ associated matrix $\widetilde{\bf W}$, which relates $H$ with $G$. This study also establishes conditions under which a main eigenvalue of $G$ is a main or non-main eigenvalue of the matrix $\widetilde{\bf W}$, when the nullity of the graph $H$ is $η>0$. In such a case, we prove that every main eigenvalue of $G$ is an eigenvalue of $\widetilde{\bf W}$ with multiplicity at least $η$ which is non-main for $\bf \widetilde{W}$ if and only if $0$ is a non-main eigenvalue of $H$. Furthermore, the spectra of the lexicographic powers of arbitrary graphs $G$ are analysed by applying the obtained results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12168 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lexicographic products and lexicographic powers of graphs -- a walk matrix approach Cardoso, Domingos M. Carvalho, Paula Gomes, Helena Pinheiro, Sofia J. Rama, Paula Combinatorics 05C50, 05C76 The characteristic polynomial and the spectrum of the lexicographic product of graphs $H[G]$, a specific instance of the generalized composition (also called $H$-join), are explicitly determined for arbitrary graphs $H$ and $G$, in terms of the eigenvalues of $G$ and an $H[G]$ associated matrix $\widetilde{\bf W}$, which relates $H$ with $G$. This study also establishes conditions under which a main eigenvalue of $G$ is a main or non-main eigenvalue of the matrix $\widetilde{\bf W}$, when the nullity of the graph $H$ is $η>0$. In such a case, we prove that every main eigenvalue of $G$ is an eigenvalue of $\widetilde{\bf W}$ with multiplicity at least $η$ which is non-main for $\bf \widetilde{W}$ if and only if $0$ is a non-main eigenvalue of $H$. Furthermore, the spectra of the lexicographic powers of arbitrary graphs $G$ are analysed by applying the obtained results. |
| title | Lexicographic products and lexicographic powers of graphs -- a walk matrix approach |
| topic | Combinatorics 05C50, 05C76 |
| url | https://arxiv.org/abs/2506.12168 |