给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图

doi:10.15960/j.cnki.issn.1007-6093.2025.01.015

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (1): 185-197.doi: 10.15960/j.cnki.issn.1007-6093.2025.01.015

给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图

杨禹¹, 朱忠熏²^,*(), 周鋆鹏²

1. 云南警官学院心理健身教研中心, 云南昆明 650221
2. 中南民族大学数学与统计学学院, 湖北武汉 430074

收稿日期:2021-12-01 出版日期:2025-03-15 发布日期:2025-03-08
通讯作者: 朱忠熏 E-mail:zzxun73@163.com
基金资助:
中央高校基本科研业务费专项资金(CZY23009)

The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius

Yu YANG¹, Zhongxun ZHU²^,*(), Junpeng ZHOU²

1. Psychological Fitness Teaching and Research Center, Yunnan Police College, Kunming 650221, Yunnan, China
2. School of Mathematics and Statistics, South-Central University for Nationalities, Wuhan 430074, Hubei, China

Received:2021-12-01 Online:2025-03-15 Published:2025-03-08
Contact: Zhongxun ZHU E-mail:zzxun73@163.com

摘要/Abstract

摘要：

对于一个$k$一致超图$H=(V, E)$, 设$B (H)$是它的关联矩阵且$\mathcal{Q}(H)=B (H) B (H)^{\top}$是它的无符号拉普拉斯矩阵。$H$的无符号拉普拉斯谱半径是$\mathcal{Q}(H)$的所有特征值的模的最大值。设$\mathcal{H}^n_{k, r}$是具有$n$个点和$r$个悬挂点的连通$k$一致超图的图类。在$\mathcal{H}^n_{k, r}$中, 对于$n-r\geq k$和某些$n-r\in[k-1]$的情形, 本文刻画了具有最大无符号拉普拉斯谱半径的极值超图。

关键词: k一致超图, 无符号拉普拉斯谱半径, 主特征向量

Abstract:

For a $k$-uniform hypergraph $H=(V, E)$, let $B(H)$ be its incidence matrix and $\mathcal{Q}(H)=B(H)B(H)^{\top}$ be its signless Laplacian matrix. The signless Laplacian spectral radius of $H$ is the maximum modulus of all eigenvalues of $\mathcal{Q}(H)$. Let $\mathcal{H}^n_{k, r}$ be the class of connected $k$-uniform hypergraphs with $n$ vertices and $r$ pendent vertices. In this paper, the extremal hypergraphs having maximum spectral radii in $\mathcal{H}^n_{k, r}$ are characterized for $n-r\geq k$ and some cases $n-r\in [k-1]$, respectively.

Key words: k-uniform hypergraph, signless Laplacian spectral radius, principal eigenvector

中图分类号:

O157.5

杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.

Yu YANG, Zhongxun ZHU, Junpeng ZHOU. The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius[J]. Operations Research Transactions, 2025, 29(1): 185-197.

图/表 7

表1

图1

图2

图3

表2

图4

图5

参考文献 15

1	Cooper J . Adjacency spectra of random and complete hypergraphs[J]. Linear Algebra and Its Applications, 2020, 596, 184- 202. doi: 10.1016/j.laa.2020.03.013
2	Cooper J , Dutle A . Spectra of uniform hypergraphs[J]. Linear Algebra and Its Applications, 2012, 436 (9): 3268- 3292. doi: 10.1016/j.laa.2011.11.018
3	Bu C , Zhou J , Wei Y . E-cospectral hypergraphs and some hypergraphs determined by their spectral[J]. Linear Algebra and Its Applications, 2014, 459, 397- 403. doi: 10.1016/j.laa.2014.07.020
4	Fan Y , Tan Y , Peng X , et al. Maximizing spectral Radii of uniform hypergraphs with few edges[J]. Discussiones Mathematicae Graph Theory, 2016, 36 (4): 845- 856. doi: 10.7151/dmgt.1906
5	Kang L , Nikiforov V , Yuan X . The p-spectral radius of k-partite and k-chromatic uniform hypergraphs[J]. Linear Algebra and Its Applications, 2015, 478, 81- 107. doi: 10.1016/j.laa.2015.03.016
6	Li H , Shao J , Qi L . The extremal spectral Radii of k-uniform supertrees[J]. Journal of Combinatorial Optimization, 2016, 32, 741- 764. doi: 10.1007/s10878-015-9896-4
7	Lu L , Man S . Connected hypergraphs with small spectral radius[J]. Linear Algebra and Its Applications, 2016, 509, 206- 227. doi: 10.1016/j.laa.2016.07.013
8	Yuan X , Shao J , Shan H . Ordering of some uniform supertrees with larger spectral Radii[J]. Linear Algebra and Its Applications, 2016, 495, 206- 222. doi: 10.1016/j.laa.2016.01.031
9	Rodriguez J . On the Laplacian eigenvalues and metric parameters of hypergraphs[J]. Linear and Multilinear Algebra, 2002, 50, 1- 14. doi: 10.1080/03081080290011692
10	Rodriguez J . On the Laplacian spectrum and walk-regular hypergraphs[J]. Linear and Multilinear Algebra, 2003, 51, 285- 297. doi: 10.1080/0308108031000084374
11	Rodriguez J . Laplacian eigenvalues and partition problems in hypergraphs[J]. Applied Mathematics Letters, 2009, 22, 916- 921. doi: 10.1016/j.aml.2008.07.020
12	Reff N , Rusnak L . An oriented hypergraphic approach to algebraic graph theory[J]. Linear Algebra and Its Applications, 2012, 437, 2262- 2270. doi: 10.1016/j.laa.2012.06.011
13	Bretto A . Hypergraph Theory: An Introduction[M]. Cham: Springer, 2013.
14	Cardoso K, Trevisan V. The signless Laplacian matrix of hypergraphs[EB/OL]. (2019-09-23)[2021-10-12]. arXiv: 1909.00246.
15	Zhang J , Li J . The maximum spectral radius of k-uniform hypergraphs with r pendent vertices[J]. Linear and Multilinear Algebra, 2019, 67 (5): 1062- 1073. doi: 10.1080/03081087.2018.1442811

$ K_n^k $	由点集$ [n] $和边集$ E $构成的$ k $一致完全超图, 其中边集$ E $是由$ [n] $中所有的$ k $-子集构成。
$ A_{n, r} $	由$ K_{n-r}^k $添加上$ r $个新的悬挂点和$ r $条新边构成的$ k $一致超图, 每条新边由$ V(K_{n-r}^k) $的$ (k-1) $-子集$ V_0 $和一个新的悬挂点组成, 其中$ n-r{\geqslant} k+1 $。
$ B_{n, r} $	点集为$ \{u_1, u_2, {\cdots}, u_k, v_1, v_2, {\cdots}, v_r\} $和边集为$ E=\{e_0, e_1, e_2, {\cdots}, e_{r-1}, e_r\} $的$ k $一致超图, 其中$ e_0=\{u_1, u_2, {\cdots}, u_k\} $, $ e_r=\{u_1, u_2, {\cdots}, u_{k-2}, u_k, v_r\} $, 对于$ i\in [r-1] $, $ e_i=\{u_1, u_2, {\cdots}, u_{k-1}, v_i\} $, 其中$ n-r=k $。
$ C_{n, r} $	具有$ n $个点和$ s $条边的超图, 其中它有$ r $个悬挂点且每条边都含有$ k-n+r $个悬挂点, $ n-r{\leqslant} k-1 $, $ r=s(k-n+r) $, 参见图 1。
$ D_{n, r} $	具有$ n $个点和$ s $条边的超图, 其中它有$ r $个悬挂点, 它的其中一条边含有$ k-n+r+1 $个悬挂点, 其余的边含有$ k-n+r $个悬挂点, $ 1{\leqslant} n-r{\leqslant} k-1, r=s(k-n+r)+1 $, 参见图 2。

$ F_{n, r}^1 $	具有$ n $个点和$ s $条边的超图, 其中它含有$ r $个悬挂点, 它的其中一条边含有$ k-n+r+2 $个悬挂点, 其余的每条边各含$ k-n+r $个悬挂点, $ 1{\leqslant} n-r{\leqslant} k-1 $, $ r=s(k-n+r)+2 $, $ s{\geqslant} 3 $, 参见图 4。
$ F_{n, r}^2 $	具有$ n $个点和$ s $条边的超图, 其中它含有$ r $个悬挂点, 有两条边都含有$ k-n+r+1 $个悬挂点且有相同的非悬挂点, 其余的每条边各含$ k-n+r $个悬挂点, $ 1{\leqslant} n-r{\leqslant} k-1 $, $ s{\geqslant} 4 $, $ r=s(k-n+r)+2 $, 参见图 4。
$ F_{n, r}^3 $	具有$ n $个点和$ 3 $条边的超图, 其中它含有$ r $个悬挂点, 有两条边含有$ k-n+r+1 $个悬挂点和不同的非悬挂点集, 第三条边含$ k-n+r $个悬挂点, 参见图 5。

[1]	余桂东, 刘珍珍, 王礼想, 李青. 可迹图的一些新充分条件[J]. 运筹学学报（中英文）, 2024, 28(1): 131-140.
[2]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[3]	余桂东, 周甫, 刘琦. 可迹图的谱充分条件[J]. 运筹学学报, 2017, 21(1): 118-124.

给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图

The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 15

相关文章 3

编辑推荐

Metrics

本文评价