Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

详细信息    查看全文

• 作者：Nair Abreu^a ; ^{nairabreunovoa@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Domingos M. Cardoso^b ; ^c ; ^{dcardoso@ua.pt" class="auth_mail" title="E-mail the corresponding author} ; Paula Carvalho^b ; ^c ; ^{paula.carvalho@ua.pt" class="auth_mail" title="E-mail the corresponding author} ; Cybele T.M. Vinagre^d ; ^{cybl@vm.uff.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph spectra ; Graph operations ; Lexicographic product of graphs
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 January 2017
• 年：2017
• 卷：340
• 期：1
• 页码：3235-3244
• 全文大小：976 K

文摘

Consider two graphs class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=eee5701ac9c753f66fe6fe84cc5c7130" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si5.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=da62f961893e35e99b6a2c50005da088" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=2d5758bd7ec7237fdff7c4c888a56daf" title="Click to view the MathML source">H^k[G]class="mathContainer hidden">class="mathCode">$H^k\left[G\right]$ be the lexicographic product of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si7.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=10a23dbf68c5c1bd2854afdcdcafed67" title="Click to view the MathML source">H^kclass="mathContainer hidden">class="mathCode">$H^k$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=eee5701ac9c753f66fe6fe84cc5c7130" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si7.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=10a23dbf68c5c1bd2854afdcdcafed67" title="Click to view the MathML source">H^kclass="mathContainer hidden">class="mathCode">$H^k$ is the lexicographic product of the graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si5.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=da62f961893e35e99b6a2c50005da088" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ by itself class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si11.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=6898e1c6a70851437d3533143284fafe" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ times. In this paper, we determine the spectrum of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=2d5758bd7ec7237fdff7c4c888a56daf" title="Click to view the MathML source">H^k[G]class="mathContainer hidden">class="mathCode">$H^k\left[G\right]$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si7.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=10a23dbf68c5c1bd2854afdcdcafed67" title="Click to view the MathML source">H^kclass="mathContainer hidden">class="mathCode">$H^k$ when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=eee5701ac9c753f66fe6fe84cc5c7130" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si5.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=da62f961893e35e99b6a2c50005da088" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ are regular and the Laplacian spectrum of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=2d5758bd7ec7237fdff7c4c888a56daf" title="Click to view the MathML source">H^k[G]class="mathContainer hidden">class="mathCode">$H^k\left[G\right]$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si7.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=10a23dbf68c5c1bd2854afdcdcafed67" title="Click to view the MathML source">H^kclass="mathContainer hidden">class="mathCode">$H^k$ for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=eee5701ac9c753f66fe6fe84cc5c7130" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302382&_mathId=si5.gif&_user=111111111&_pii=S0012365X16302382&_rdoc=1&_issn=0012365X&md5=da62f961893e35e99b6a2c50005da088" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$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¹⁰⁰ ) 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.