Back to Search
Start Over
Maxima of the Q-index: graphs with no K_s,t
- 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 :
- Mathematics - Combinatorics
05C50
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1507.00625
- Document Type :
- Working Paper