Abstract | ||
---|---|---|
Let G be a graph on n vertices with spectral radius lambda (this is the largest eigen-value of the adjacency matrix of G). We show that if G does not contain the complete bipartite graph K-t,K-s as a subgraph, where 2 <= t <= s, then lambda <= ((s - 1)(1/t) + o(1))n(1-1/t) for fixed t and s while n --> infinity. Asymptotically, this bound matches the Kovari-Turan-Sos upper bound on the average degree of G (the Zarankiewicz problem). |
Year | Venue | Keywords |
---|---|---|
2009 | ELECTRONIC JOURNAL OF COMBINATORICS | adjacency matrix,spectral radius,complete bipartite graph |
Field | DocType | Volume |
Adjacency matrix,Discrete mathematics,Complete bipartite graph,Combinatorics,Spectral radius,Vertex (geometry),Upper and lower bounds,Zarankiewicz problem,Mathematics,Eigenvalues and eigenvectors,Lambda | Journal | 16.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 2 |
PageRank | References | Authors |
0.47 | 4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Laszlo Babai | 1 | 3537 | 573.58 |
Barry Guiduli | 2 | 38 | 4.66 |