论文标题
连接图中的最大S-cliques数量及其在光谱时刻的应用
The maximum number of s-cliques in connected graphs and its application to spectral moment
论文作者
论文摘要
关于完整子图的数量的极端问题在极端图理论中有一个长篇小说。令$ k_s（g）$为图$ g $中的$ s $ cliques的数量，$ m = {{r_m} \ select s}}+t_m $，其中$ 0 \ le t_m \ leq r_m $。 EDRőS表明，$ k_s（g）\ le {{r_m} \ select s}+{{t_m} \ size $ m $和订购$ n \ geq r_m+1 $的所有图表上的所有图表上所有图表上的所有图表上。 ％清楚，$ k_ {r_m}^{t_m} \ cup（n-r_m-1）k_1 $是一个极端图，其中$ k_ {r_m}^{t_m} $是将新顶点加入$ k_ {r_m} $的新顶点。考虑在连接情况下进行改进是很自然的：在所有尺寸$ m $和订单$ n $的连接图上，$ s $ cliques的最大数量是多少？在本文中，获得了$ k_s（g）$的锋利上限，并且极端图是完全表征的。该技术和界限与通常的情况不同。作为应用程序，该结果可用于在光谱时刻解决问题。
Extremal problems concerning the number of complete subgraphs have a long story in extremal graph theory. Let $k_s(G)$ be the number of $s$-cliques in a graph $G$ and $m={{r_m}\choose s}+t_m$, where $0\le t_m\leq r_m$. Edrős showed that $k_s(G)\le {{r_m}\choose s}+{{t_m}\choose{s-1}}$ over all graphs of size $m$ and order $n\geq r_m+1$. %Clearly, $K_{r_m}^{t_m}\cup (n-r_m-1)K_1$ is an extremal graph, where $K_{r_m}^{t_m}$ is the graph by joining a new vertex to $t_m$ vertices of $K_{r_m}$. It is natural to consider an improvement in connected situation: what is the maximum number of $s$-cliques over all connected graphs of size $m$ and order $n$? In this paper, the sharp upper bound of $k_s(G)$ is obtained and extremal graphs are completely characterized. The technique and the bound are different from those in general case. As an application, this result can be used to solve a question on spectral moment.
