Spectral Extremal Graphs for Disjoint Cliques

[摘要] Let $kK_{r+1}$ be the graph consisting of $k$ vertex-disjoint copies of the complete graph $K_{r+1}$. Moon [Canad. J. Math. 20 (1968) 95--102] and Simonovits [Theory of Graphs (Proc. colloq., Tihany, 1996)] independently showed that if $n$ is sufficiently large, then the join of a complete graph $K_{k-1}$ and an $r$-partite Turán graph $T_{n-k+1,r}$ is the unique extremal graph for $kK_{r+1}$. In this paper we consider the graph which has the maximum spectral radius among all graphs without $k$ disjoint cliques. We show that if $G$ attains the maximum spectral radius over all $n$-vertex $kK_{r+1}$-free graphs for sufficiently large $n$, then $G$ is isomorphic to the join of a complete graph $K_{k-1}$ and an $r$-partite Turán graph $T_{n-k+1,r}$.

[学科分类] 统计和概率