论文标题
组合绑定在图的不同特征值的数量上
A combinatorial bound on the number of distinct eigenvalues of a graph
论文作者
论文摘要
图$ g $的最少数量的不同特征值（用$ q（g）$表示）具有与图中独特最短路径的组合绑定。特别是，$ q（g）$在下面以$ k $为界，其中$ k $是$ g $中任何一对顶点的独特最短路径的顶点数量。因此，如果$ n $是$ g $的顶点的数量，则$ n-q（g）$在上面的限制在上面的汇编大小（相对于$ g $的顶点集）的顶点集的最长独特路径的顶点集，与$ g $的任何一对顶点相连。本文的目的是开始研究$ n-k $的次要主持酮地板，这是所有图表中的最低$ n-k $的最低图表。因此，我们证明了有关此次要量音底层的一些结果。
The smallest possible number of distinct eigenvalues of a graph $G$, denoted by $q(G)$, has a combinatorial bound in terms of unique shortest paths in the graph. In particular, $q(G)$ is bounded below by $k$, where $k$ is the number of vertices of a unique shortest path joining any pair of vertices in $G$. Thus, if $n$ is the number of vertices of $G$, then $n-q(G)$ is bounded above by the size of the complement (with respect to the vertex set of $G$) of the vertex set of the longest unique shortest path joining any pair of vertices of $G$. The purpose of this paper is to commence the study of the minor-monotone floor of $n-k$, which is the minimum of $n-k$ among all graphs of which $G$ is a minor. Accordingly, we prove some results about this minor-monotone floor.
