English

运筹学学报

• 运筹学 •    

单圈图的次大(拉普拉斯) 分离度

余桂东,阮征,舒阿秀,于涛   

  1. 安庆师范大学
  • 收稿日期:2018-03-21 修回日期:2018-06-12 发布日期:2019-03-05
  • 通讯作者: 余桂东

The second maximum (Laplacian)separator

  • Received:2018-03-21 Revised:2018-06-12 Published:2019-03-05

摘要： 设~$G$ 是一个~$n$ 阶单圈图, $\lambda_{1}(G)$、 $\lambda_{2}(G)$ 分别为图~$G$ 的邻接矩阵的最大特征值与次大特征值, $\mu_{1}(G)$、 $\mu_{2}(G)$ 分别为图~$G$ 的拉普拉斯 矩阵的最大特征值与次大特征值. 图~$G$ 的分离度定义为~$S_{A}(G)=\lambda_{1}(G)-\lambda_{2}(G)$, 拉普拉斯 分离度定义为~$S_{L}(G)=\mu_{1}(G)-\mu_{2}(G)$. 本文研究了给定阶数的单圈图的次大分离度和次大拉普拉斯分离度, 并刻画了相应的极图.

关键词: 单圈图, 分离度, 拉普拉斯分离度

Abstract: Let $G$ be a unicyclic graph of order $n$, $\lambda_{1}(G)$ and $\lambda_{2}(G)$ be the largest eigenvalue and second largest eigenvalue of the adjacent matrix of $G$, $\mu_{1}(G)$ and $\mu_{2}(G)$ be the largest eigenvalue and second largest eigenvalue of the Laplacian matrix of $G$, respectively. The separator of $G$ is defined as $S_{A}(G)=\lambda_{1}(G)-\lambda_{2}(G)$. The Laplacian separator of $G$ is defined as $S_{L}(G)=\mu_{1}(G)-\mu_{2}(G)$. In this paper, we respectively study the second maximum separator and second maximum Laplacian separator of unicyclic graphs with given order, and characterize the according extremal graphs.

Key words: Unicyclic graph, separator, Laplacian separator