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

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

Abstract

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

CLC Number:

O157.5

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.

Figures/Tables 7

References 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]	Guidong YU, Zhenzhen LIU, Lixiang WANG, Qing LI. Some new sufficient condition on traceable graphs [J]. Operations Research Transactions, 2024, 28(1): 131-140.
[2]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[3]	YU Guidong, ZHOU Fu, LIU Qi. Spectral sufficient conditions on traceable graphs [J]. Operations Research Transactions, 2017, 21(1): 118-124.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 15

Related Articles 3

Recommended Articles

Metrics

Comments