Proof of conjectures on adjacency eigenvalues of graphs
Proof of conjectures on adjacency eigenvalues of graphs
复制标题
DOI：
10.1016/j.disc.2012.09.017
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
K. Das
中科院分区：
文献类型：
--
作者：
K. Das
设G是一个n阶简单图，其中t是三角形.设λ1（G），λ2（G），…，λn（G）为图G的邻接矩阵的特征值. X. Yong [X. Yong，关于简单无向图特征值的分布，Linear Algebra Appl.295（1999）73-80]推测（i）G是完全的当且仅当det（A（G））=（-1）n-1（n-1）并且（ii）G是完全的当且仅当|det（A（G））|=n−1。这里我们用一个反例来反驳这个猜想。Wang等人[杰夫Wang，F.贝拉多，Q.X.黄，B。Borovianin，On the two largest Q-eigenvalues of graphs，Discrete Math.310（2010）2858-2866]证明了友谊图F是由它的邻接谱决定的。我们在这里证明这个猜想。一个顶点的偏心率是它到另一个顶点的最大距离，图G的平均偏心率ecc（G）是图G所有顶点的偏心率的平均值。此外，我们提到了AutoGraphiX系统获得的关于图的平均偏心率（ecc（G））、围长（g（G））和谱半径（λ1（G））的三个图（参见Aouchiche（2006）[1]，可在http：//www.gerad.ca/gravagx/在线获得）。给出了一个猜想的证明，并通过反例反证了两个猜想。
Let G be a simple graph of order n with t triangle(s). Also let λ1(G),λ2(G),…,λn(G) be the eigenvalues of the adjacency matrix of graph G. X. Yong [X. Yong, On the distribution of eigenvalues of a simple undirected graph, Linear Algebra Appl. 295 (1999) 73–80] conjectured that (i) G is complete if and only if det(A(G))=(−1)n−1(n−1) and also (ii) G is complete if and only if |det(A(G))|=n−1. Here we disprove this conjecture by a counter example. Wang et al. [J.F. Wang, F. Belardo, Q.X. Huang, B. Borovićanin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010) 2858–2866] conjectured that friendship graph Ftis determined by its adjacency spectrum. Here we prove this conjecture. The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity ecc(G) of a graph G is the mean value of eccentricities of all vertices of G. Moreover, we mention three conjectures, obtained by the system AutoGraphiX, about the average eccentricity (ecc(G)), girth (g(G)) and the spectral radius (λ1(G)) of graphs (see Aouchiche (2006) [1], available online at http://www.gerad.ca/~agx/). We give a proof of one conjecture and disprove two conjectures by counter examples.