Back to Search Start Over

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

Authors :
de Freitas, Maria Aguieiras A.
Nikiforov, Vladimir
Patuzzi, Laura
Publication Year :
2015

Abstract

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 $K_{2,s+1},$ then the largest eigenvalue $q(G)$ of the signless Laplacian of $G$ satisfies \[ q(G)\leq\frac{n+2s}{2}+\frac{1}{2}\sqrt{(n-2s)^{2}+8s}, \] with equality holding if and only if $G$ is a join of $K_{1}$ and an $s$-regular graph of order $n-1.$<br />Comment: 10 p

Subjects

Subjects :
Mathematics - Combinatorics
05C50

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1507.00625
Document Type :
Working Paper