ABSTRACT

A necessary and sufficient condition for graphs with k distinct eigenvalues is determined for Q- matrix and adjacency matrix.

Keywords:Q-Matrix, Adjacency Matrix, Eigenvalue, Graph Spectrum

具有不同特征值的连通图

李国政

青海师范大学数学系，青海 西宁

收稿日期：2016年2月2日；录用日期：2016年2月21日；发布日期：2016年2月24日

摘 要

关于图的Q-矩阵和邻接矩阵，给出了具有k个不同特征值的连通图的充分必要条件。

关键词 :Q-矩阵，邻接矩阵，特征值，图的谱

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个不同的实数满足下面的条件

(i)是一个不可逆矩阵，；

(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)。

文章引用

李国政. 具有不同特征值的连通图
Connected Graphs with Distinct Eigenvalues[J]. 应用数学进展, 2016, 05(01): 59-62. http://dx.doi.org/10.12677/AAM.2016.51009

参考文献 (References)