1. 引言
本文仅考虑有限无向简单连通图(即不含环和重边)。令表示点集为，边集为的图，它的阶数为。图G的Q-矩阵定义为，其中和分别表示图G的邻接矩阵和度矩阵。图G的Q-特征值和邻接特征值就是其Q-矩阵和邻接矩阵的特征值。由于是实对称的半正定矩阵，故图G的Q-特征值是非负实数，并且设为。
近来，Q-矩阵(在[1] 中被命名)吸引了很多研究者的兴趣，文 [2] 以及随后的文 [3] - [5] 提出并规范了图的Q-谱理论。Q-矩阵是一个很好的工具，因为它的谱性质在很多方面优于拉普拉斯矩阵和。关于这方面的结果可参见上述文献。因此，本文将重点研究图的Q-谱。
Doom [6] 首先研究了具有不同邻接特征值的连通图。后来，Van Dam [7] - [10] 对这个问题作出了很多重要的贡献。关于具有不同Q-特征值的连通图，Ayoobi等 [11] 指出具有两个不同Q-特征值的连通图是完全图，并研究了有三个不同Q-特征值的图。本文将研究具有k不同Q-特征值的连通图。
为了证明本文的主要结果，首先引入矩阵理论中的结果 [12] 。设和分别表示实数集和n阶的实矩阵。
性质1 设。
(i) B是对角矩阵的充要条件是B的特征值在中，并且每个特征值的代数重数与几何重数相等。
(ii) 设B所有不同的特征值为。则B是对角矩阵的充要条件是其最小多项式为。
(iii) B的秩等于1的充要条件是存在两个非零的实n维向量x和y，使得。
2. 主要结果
用O和I分别表示零矩阵和单位矩阵。
定理2.1. 设G是一个阶为n的连通图。G存在个不同Q-特征值的充要条件是存在k个不同的实数满足下面的条件
(i)是一个不可逆矩阵，；
(ii)，其中是属于特征值的特征向量。而且，正是G的k个不同的Q-特征值。
证明：令是图G的k个不同的Q-特征值。由性质1 (ii)得Q的最小多项式是
，
从而有
。 (1)
设，其中。由于G是连通图，那么的代数重数等于1，从而由性质1 (i)得的几何重数也是1。因此，在G中任何关于的特征向量都是的倍数。所以，通过(1)得矩阵的每列都可用的形式表示，其中。从而
。 (2)
由于，在(2)的两边乘以得
其中是欧几里得范数。故对于，
。
必要性得证。
下证充分性。由齐次线性方程组的性质知：由(i)得有一个非零解，不妨设为。故有，这表明是矩阵的特征值。由(ii)得是矩阵Q的一个特征值。至此得到了G的k个不同的特征值。假设G除此之外还存在其它的特征值。令。则易得是的特征值。显然，，且。通过(ii)和性质1(iii)知，的秩是1。故仅有一个非零特征值，矛盾，得证。
众所周知，若G是连通图，邻接矩阵和Q-矩阵的上述性质相同。故定理也对邻接矩阵成立。从而有下面的结果：
定理2.2. 设G是一个阶为n的连通图。G存在个不同邻接特征值的充要条件是存在k个不同的实数满足下面的条件
(ii)，其中是属于特征值的特征向量。而且，正是G的k个不同的邻接特征值。
关于图的直径和不同邻接特征值的个数有以下的关系 [13] ，本文采用定理2.2给出一个新的证明方法。
推论2.1. 设G是连通图且有k个不同的邻接特征值。则图的直径至多是。
证明：由定理2.2(ii)得
(3)
因为是正特征向量，则。假设。由直径的定义知，对于顶点和，矩阵的元满足
这连同(3)得
矛盾。故。
注记2.2. Ayoob等 [11] 研究具有三个不同的Q-特征值，他们的定理 [11] 恰是定理2.1中的特殊情况。
注记2.3. Harary和Schwenk在四十年前提出问题：哪些图具有完全不同的邻接特征值？定理2.2中的情形给出了此问题的代数条件，进一步需要研究的问题就是如何利用此条件刻画图的结构。
基金项目
国家自然科学基金青年科学基金(编号11101232)，国家自然科学基金(编号11461054)。
参考文献