Maxima of the Q-index: Graphs with no K_s,t

详细信息    查看全文

• 作者：Maria Aguieiras A. de Freitas^a ; ^{maguieiras@im.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Vladimir Nikiforov^b ; ^{vnikifrv@memphis.edu" class="auth_mail" title="E-mail the corresponding author} ; Laura Patuzzi^a ; ^{laura@im.ufrj.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 May 2016
• 年：2016
• 卷：496
• 期：Complete
• 页码：381-391
• 全文大小：284 K

文摘

This note presents a new spectral version of the graph Zarankiewicz problem: How large can be the maximum eigenvalue of the signless Laplacian of a graph of order n that does not contain a specified complete bipartite subgraph. A conjecture is stated about general complete bipartite graphs, which is proved for infinitely many cases.

More precisely, it is shown that if G is a graph of order n  , with no subgraph isomorphic to 16000902&_mathId=si1.gif&_user=111111111&_pii=S0024379516000902&_rdoc=1&_issn=00243795&md5=011bc3a776a03ec65d6d271f10ee3223" title="Click to view the MathML source">K_2,s+1$K_{2,s+1}$, then the largest eigenvalue 16000902&_mathId=si2.gif&_user=111111111&_pii=S0024379516000902&_rdoc=1&_issn=00243795&md5=491e7a620f19a9e668ff69b919d207b2" title="Click to view the MathML source">q(G)$q(G)$ of the signless Laplacian of G satisfies

with equality holding if and only if G   is a join of 16000902&_mathId=si4.gif&_user=111111111&_pii=S0024379516000902&_rdoc=1&_issn=00243795&md5=d8d3171e7e8e9abe7d443e64afc12950" title="Click to view the MathML source">K₁$K_1$ and an s  -regular graph of order 16000902&_mathId=si41.gif&_user=111111111&_pii=S0024379516000902&_rdoc=1&_issn=00243795&md5=ff8972083fab400c40d5c744f7b26d30" title="Click to view the MathML source">n−1$n-1$.