图变换及其在图的最小无符号拉普拉斯特征值的应用北大核心CSCD

假定G是一个带有点集V(G)={v_(1),v_(2),···,v_(n)}的连通简单图,图G的邻接矩阵A(G)=(a_(ij))_(n×n),其中点vi与点vj相邻,则a_(ij)=1;否则a_(ij)=0。我们定义度矩阵D(G)=diag(dG(v_(1)),dG(v_(2)),···,dG(v_(n))),其中dG(v_(i))是图G中点v_(i)(1≤i≤n)的度数。定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G),因为Q(G)是一个半正定矩阵,所以可将其特征值设为λ_(1)(G)≥λ_(2)(G)≥···≥λ_(n)(G)≥0,其中特征值λn(G)也称为图G的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究,报告了相关问题的研究现状,给出了两种图变换,并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。

The Graft Transformations and Their Applications on the Least Signless Laplacian Eigenvalue of Graphs

Suppose that $G$ is a simple connected graph with the vertex set $V(G)=\{v_1,v_2,$ $\cdots,v_n\}$. Then the adjacency matrix of $G$ is $A(G)=(a_{ij})_{n\times n}$, where $a_{ij}=1$ if $v_i$ is adjacent to $v_j$, and otherwise $a_{ij}=0$. The degree matrix $D(G)={\rm diag}(d_{G}(v_1), d_{G}(v_2),\cdots,d_{G}(v_n))$, where $d_{G}(v_i)$ denotes the degree of $v_i$ in the graph $G(1\leq i\leq n)$. The matrix $Q(G)=D(G)+A(G)$ is the signless Laplacian matrix of $G$. Since $Q(G)$ is positive semidefinite, its eigenvalues can be arranged as $\lambda_1(G)\geq \lambda_2(G)\geq \cdots \geq \lambda_n(G)\geq 0$, where $\lambda_n(G)$ is the least signless Laplacian eigenvalue of $G$. The least signless Laplacian eigenvalues is investigated for the complements of graphs and the state of art of the relevant issues is summarized. By virtue of two graft transformations obtained by us, the unique connected graph is characterized, whose least signless Laplacian eigenvalue is minimum among the complements of all bicyclic graphs.