具有不同特征值的连通图 Connected Graphs with Distinct Eigenvalues
 

Advances in Applied Mathematics
Vol.05 No.01(2016), Article ID:16978,4 pages
10.12677/AAM.2016.51009

Connected Graphs with Distinct Eigenvalues

Guozheng Li

Department of Mathematics, Qinghai Normal University, Xining Qinghai

Received: Feb. 2nd, 2016; accepted: Feb. 21st, 2016; published: Feb. 24th, 2016

Copyright © 2016 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

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)

  1. 1. Haemers, W.H. and Spence, E. (2004) Enumeration of Cospectral Graphs. European Journal of Combinatorics, 25, 199-211. http://dx.doi.org/10.1016/S0195-6698(03)00100-8

  2. 2. Cvetković, D., Rowlinson, P. and Simić, S.K. (2007) Signless Laplacian of Finite Graphs. Linear Algebra and Its Applications, 423, 155-171. http://dx.doi.org/10.1016/j.laa.2007.01.009

  3. 3. Cvetković, D. and Simić, S.K. (2009) Towards a Spectral Theory of Graphs Based on Signless Laplacian, I. Publications de l’Institut Mathématique (Beograd) (N.S.), 85, 19-33.

  4. 4. Cvetković, D. and Simić, S.K. (2010) Towards a Spectral Theory of Graphs Based on Signless Laplacian, II. Linear Algebra and Its Applications, 432, 2257-2272. http://dx.doi.org/10.1016/j.laa.2009.05.020

  5. 5. Cvetković, D. and Simić, S.K. (2010) Towards a Spectral Theory of Graphs Based on Signless Laplacian, III. Applicable Analysis and Discrete Mathematics, 4, 156-166. http://dx.doi.org/10.2298/AADM1000001C

  6. 6. Doob, M. (1970) Graphs with a Small Number of Distinct Eigenvalues. Annals of the New York Academy of Sciences, 175, 104-110. http://dx.doi.org/10.1111/j.1749-6632.1970.tb56460.x

  7. 7. van Dam, E.R. (1996) Graphs with Few Eigenvalues. An Interplay between Combinatorics and Algebra. Center Dissertation Series 20, Thesis, Tilburg University, Til-burg.

  8. 8. van Dam, E.R. (1998) Graphs with Few Distinct Eigenvalues, Where Most of the Times Few Means Three or Four. Journal of Combinatorial Theory, Series B, 73, 101-118. http://dx.doi.org/10.1006/jctb.1998.1815

  9. 9. van Dam, E.R. and Haermers, W.H. (1998) Graphs with Constant and . Discrete Mathematics, 182, 293-307.

  10. 10. van Dam, E.R. and Spenceb, E. (1998) Small Regular Graphs with Four Eigenvalues. Discrete Mathematics, 189, 233-257. http://dx.doi.org/10.1016/S0012-365X(98)00085-5

  11. 11. Ayoobi, F., Omidi, G.R. and Tayfeh-Rezaie, B. (2011) A Note on Graphs Whose Signless Laplacian Has Three Distinct Eigenvalues. Linear Multilinear Algebra, 59, 701-706. http://dx.doi.org/10.1080/03081087.2010.489900

  12. 12. Horn, R.A. and Johnson, C.R. (1986) Matrix Analysis. Cambridge University Press, Cambridge.

  13. 13. Cvetković, D., Doob, M. and Sachs, H. (1995) Spectra of Graphs-Theory and Applications III. Johan Ambrosius Bart Verlag, Heidelberg-Leipzig.

期刊菜单