论文标题
$ k_ {r+1} $ - 带有小光谱半径的饱和图
$K_{r+1}$-saturated graphs with small spectral radius
论文作者
论文摘要
对于图$ h $，如果$ g $不包含$ h $作为子图，则图$ g $为$ h $饱和，而是e（\ overline {g}）$，$ g+e $包含$ h $的任何$ e \。在本说明中，我们证明了路径数量的急剧下限，长度为$ 2 $ in $ n $ vertex $ k_ {r+1} $ - 饱和图。然后，我们使用此界限，在此类图的光谱半径上给出一个下限，对于每个固定的$ r $和$ n \ to \ infty $，这些图形均不紧密。
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e \in E(\overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to\infty$.
