Sign in
Degenerate Turán Problems for Hereditary Properties
Journal article   Open access  Peer reviewed

Degenerate Turán Problems for Hereditary Properties

Vladimir Nikiforov, Michael Tait and Craig Timmons
The Electronic journal of combinatorics, Vol.25(4)
11/30/2018
Handle:
https://hdl.handle.net/20.500.12741/rep:3589

Abstract

Let $H$ be a graph and $t\geqslant s\geqslant 2$ be integers. We prove that if $G$ is an $n$-vertex graph with no copy of $H$ and no induced copy of $K_{s,t}$, then $\lambda(G) = O\left(n^{1-1/s}\right)$ where $\lambda(G)$ is the spectral radius of the adjacency matrix of $G$. Our results are motivated by results of Babai, Guiduli, and Nikiforov bounding the maximum spectral radius of a graph with no copy (not necessarily induced) of $K_{s,t}$.
url
https://doi.org/10.37236/6775View
Published (Version of record) Open

Metrics

6 Record Views

Details