运筹学学报 ›› 2011, Vol. ›› Issue (3): 19-28.

• 论文 • 上一篇    下一篇

给定顶点数和边数的连通图的Q-谱半径

陈琳1,黄琼湘2,2   

  1. 1. 新疆医科大学医学工程技术学院数学教研室
    2. 新疆大学数学与系统科学学院
  • 收稿日期:2011-02-09 修回日期:2011-05-16 出版日期:2011-09-15 发布日期:2011-09-29
  • 通讯作者: 陈琳 E-mail:yuehuacl@163.com

The Q-spectral radii of connected graphs with given number of vertices and edges

 CHEN  Lin, HUANG  Qiong-Xiang   

  • Received:2011-02-09 Revised:2011-05-16 Online:2011-09-15 Published:2011-09-29

摘要: 图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和, 其特征值记为$q_1\geq q_2\geq \cdots \geq q_n$. 设$\mathscr{C}(n,m)$是由$n$个顶点$m$条边的连通图构成的集合, 这里$1\leq n-1\leq\ m \leq\bigl(\begin{smallmatrix}n\\2\end{smallmatrix}\bigr)$. 图$G^\star \in \mathscr{C}(n,m)$叫做最大图, 如果对于任意的$G\in \mathscr{C}(n,m)$都有$\ q_1(G^\star )\geq q_1(G)$ 成立. 在这篇文章中, 我们证明了对任意给定的正整数 $a=m-n+1$, 如果 $n>-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 那么$n-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 就有$q_1(G)

Abstract: The signless Laplacian matrix of a graph is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are denoted by $q_1\geq q_2\geq,\cdots ,\geq q_n$. Let $\mathscr{C}(n,m)$ be a set of connected graphs in which every graph has $n$ vertices and $m$ edges, where $1\leq n-1\leq\ m \leq\bigl(\begin{smallmatrix}n\\2\end{smallmatrix}\bigr)$. A graph $G^\star \in \mathscr{C}(n,m)$ is called maximum if $\ q_1(G^\star )\geq q_1(G)$ for any $G\in \mathscr{C}(n,m)$. In this paper, we proved that for any given positive integer $a=m-n+1$, $n-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, which leads to $q_1(G)-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$.