On Brouwer's conjecture for the sum of k largest Laplacian eigenvalues of graphs
On Brouwer's conjecture for the sum of k largest Laplacian eigenvalues of graphs
复制标题
关于图的 k 个最大拉普拉斯特征值之和的布劳威尔猜想
DOI：
10.1016/j.laa.2019.05.029
复制
发表时间：
2019-10
影响因子：
1.1
通讯作者：
Xiaodan Chen
中科院分区：
文献类型：
--
作者：
Xiaodan Chen
Let $G$ be a simple graph with $n$ vertices. For $1\leq k\leq n$, denote by $\mathcal{S}_k(G)$ the sum of $k$ largest Laplacian eigenvalues of $G$. It is conjectured by Brouwer that $\mathcal{S}_k(G)\leq e(G)+{k+1 \choose 2}$, where $e(G)$ is the number of edges in $G$. This conjecture has been proved to be true for $k=1$, $k=2$, $k=n-1$, and $k=n$ (for all graphs), and for certain classes of graphs such as trees, unicyclic graphs, and bicyclic graphs (for all $k\in\{1,2,\ldots,n\}$). In this paper, we show that if Brouwer's conjecture is true for all graphs when $k=p$ $(1\leq p\leq (n-1)/2)$, then it is also true for all graphs when $k=n-p-1$, from which Brouwer's conjecture follows automatically for all graphs when $k=n-2$ and $k=n-3$. We also show that for a given graph $G$ and its complement $\overline{G}$, if $\mathcal{S}_k(G)\leq e(G)+{k+1 \choose 2}$ holds for all $k$, then $\mathcal{S}_k(\overline{G})\leq e(\overline{G})+{k+1 \choose 2}$ holds for all $k$ as well, which implies that Brouwer's conjecture holds for the complements of trees, uncyclic graphs, and bicyclic graphs (for all $k$).
Let $G$ be a simple graph with $n$ vertices. For $1\leq k\leq n$, denote by $\mathcal{S}_k(G)$ the sum of $k$ largest Laplacian eigenvalues of $G$. It is conjectured by Brouwer that $\mathcal{S}_k(G)\leq e(G)+{k+1 \choose 2}$, where $e(G)$ is the number of edges in $G$. This conjecture has been proved to be true for $k=1$, $k=2$, $k=n-1$, and $k=n$ (for all graphs), and for certain classes of graphs such as trees, unicyclic graphs, and bicyclic graphs (for all $k\in\{1,2,\ldots,n\}$). In this paper, we show that if Brouwer's conjecture is true for all graphs when $k=p$ $(1\leq p\leq (n-1)/2)$, then it is also true for all graphs when $k=n-p-1$, from which Brouwer's conjecture follows automatically for all graphs when $k=n-2$ and $k=n-3$. We also show that for a given graph $G$ and its complement $\overline{G}$, if $\mathcal{S}_k(G)\leq e(G)+{k+1 \choose 2}$ holds for all $k$, then $\mathcal{S}_k(\overline{G})\leq e(\overline{G})+{k+1 \choose 2}$ holds for all $k$ as well, which implies that Brouwer's conjecture holds for the complements of trees, uncyclic graphs, and bicyclic graphs (for all $k$).
登录
查看更多内容
DOI：
10.1016/j.mcm.2011.12.047
发表时间：
2012-08
期刊：
Math. Comput. Model.
影响因子：
--
作者：
Shouzhong Wang;Yufei Huang;Bolian Liu
通讯作者：
Shouzhong Wang;Yufei Huang;Bolian Liu
影响因子：
0.8
作者：
GRONE, R;MERRIS, R
通讯作者：
MERRIS, R
DOI：
10.1090/s0002-9947-2011-05393-6
发表时间：
2009-11
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
Hua Bai
通讯作者：
Hua Bai
DOI：
10.1017/cbo9780511801518
发表时间：
2009-10
期刊：
--
影响因子：
--
作者：
D. Cvetkovic;P. Rowlinson;S. Simic
通讯作者：
D. Cvetkovic;P. Rowlinson;S. Simic
影响因子：
1.1
作者：
H. A. Ganie;A. Alghamdi;S. Pirzada
通讯作者：
H. A. Ganie;A. Alghamdi;S. Pirzada