在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2022, Vol. 39 ›› Issue (4): 631-647.doi: 10.3969/j.issn.1005-3085.2022.04.011

• • 上一篇    下一篇

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

冯小芸,   陈  旭,   王国平   

  1. 新疆师范大学数学科学学院，乌鲁木齐 830017
  • 出版日期:2022-08-15 发布日期:2022-10-15
  • 通讯作者: 王国平 E-mail: xj.wgp@163.com
  • 基金资助:
    国家自然科学基金 (11461071)；自治区研究生创新项目 (XJ2021G253).

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

FENG Xiaoyun,   CHEN Xu,   WANG Guoping   

  1. School of Mathematical Sciences, Xinjiang Normal University, Urumqi 830017
  • Online:2022-08-15 Published:2022-10-15
  • Contact: G. Wang. E-mail address: xj.wgp@163.com
  • Supported by:
    The National Natural Science Foundation of China (11461071); the Postgraduate Innovation of the Autononmous Pegion (XJ2021G253).

PDF (PC)

66

摘要： 假定$G$是一个带有点集$V(G)=\{v_1, v_2,\cdots,v_n\}$的连通简单图，图$G$的邻接矩阵$A(G)=(a_{ij})_{n\times n}$，其中点$v_i$与点$v_j$相邻，则$a_{ij}=1$；否则$a_{ij}=0$。我们定义度矩阵$D(G)={\rm diag}(d_{G}(v_1), d_{G}(v_2),\cdots,d_{G}(v_n))$，其中$d_{G}(v_i)$是图$G$中点$v_i(1\leq i\leq n)$的度数。定义图$G$的无符号拉普拉斯矩阵$Q(G)=D(G)+A(G)$，因为$Q(G)$是一个半正定矩阵，所以可将其特征值设为$\lambda_1(G)\geq \lambda_2(G)\geq \cdots \geq \lambda_n(G)\geq 0$，其中特征值$\lambda_n(G)$也称为图$G$的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究，报告了相关问题的研究现状，给出了两种图变换，
并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。

关键词: 图的变换, 最小无符号拉普拉斯特征值, 双圈图, 补图

Abstract:

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.

Key words: graft transformation, least signless Laplacian eigenvalue, bicyclic graph, complement

中图分类号: