您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (11): 165-174.doi: 10.6040/j.issn.1671-9352.0.2022.062

•   • 上一篇    

一类图的广义特征多项式

王冉冉(),文飞*(),张树成   

  1. 兰州交通大学应用数学研究所, 甘肃 兰州 730070
  • 收稿日期:2022-01-19 出版日期:2023-11-20 发布日期:2023-11-07
  • 通讯作者: 文飞 E-mail:wangrr2028@163.com;wenfei@lzjtu.edu.cn
  • 作者简介:王冉冉(1999—), 女, 硕士研究生, 研究方向为图谱理论. E-mail: wangrr2028@163.com
  • 基金资助:
    国家自然科学基金资助项目(11961041);国家自然科学基金资助项目(12261055);甘肃省自然科学基金(21JR11RA065)

On the generalized characteristic polynomial of a family of graphs

Ranran WANG(),Fei WEN*(),Shucheng ZHANG   

  1. Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2022-01-19 Online:2023-11-20 Published:2023-11-07
  • Contact: Fei WEN E-mail:wangrr2028@163.com;wenfei@lzjtu.edu.cn

RichHTML

0

PDF (PC)

344

摘要：

首先定义了一类新图——类似门槛图, 然后结合算法设计得到了这类图的广义特征多项式(即Φ-谱), 从而推出了一类门槛图的Φ-特征多项式及其谱。作为应用, 还构造了一些Φ-同谱无穷类。

关键词: 门槛图, 广义特征多项式, Φ-同谱

Abstract:

Firstly, a class of graphs called thresholdlike graphs is defined. Then, combined with algorithm, the generalized characteristic polynomial (i.e., Φ-spectrum) of such graphs is obtained. The Φ-characteristic polynomial and its spectrum of a class of threshold graphs are derived. As an application, some infinite classes of Φ-cospectra have also been constructed.

Key words: threshold graph, generalized characteristic polynomial, Φ-cospectral

中图分类号: 

  • O157.5

图1

构造图例"

表1

当m=1, 2, 3, 4时的ΦΓ(λ, t)"

m ΦΓ(λ, t)
1 $(\lambda+t)^2-1$
2 $\lambda^4+8 t \lambda^3+\left(23 t^2-4\right) \lambda^2+2\left(14 t^3-7 t-1\right) \lambda+(t-1)(2 t+1)\left(6 t^2+3 t-1\right)$
3 $\lambda^6+18 t \lambda^5+\left(130 t^2-9\right) \lambda^4+2\left(240 t^3-49 t-5\right) \lambda^3+\left(949 t^4-376 t^2-68 t+3\right) \lambda^2+2\left(471 \times t^5-297 t^3-68 t^2+12 t+2\right) \lambda$
$+(t-1)(3 t+1)\left(120 t^4+80 t^3-13 t^2-8 t+1\right)$
4 $\lambda^8+32 t \lambda^7+2\left(217 t^2-8\right) \lambda^6+4\left(812t^3-89t-7\right) \lambda^5+\left(14 609t^4-3 154 t^2-464t+2\right) \lambda^4+2\left(20 104t^5-7 073t^3-1 436t^2+49t+12\right) \lambda^3$
$+2\left(32 798 t^6-16 782 t^4-4 097 t^3+399 t^2+119 t+1\right) \lambda^2+2\left(28 656 t^7-19 710 t^5+2\left(28 656 t^7-19 710 t^5-5 297 t^4+1 072 t^3\right.\right.$
$\left.+332 t^2-10 t-3\right) \lambda+(t-1)(4 t+1)\left(5 040 t^6+3 780 t^5-392 t^4-483 t^3+5 t^2+15 t-1\right)$

图2

图G0和H0"

图3

图Gi和Hi(i=1, 2, 3)"

1 VAN DAM E R , HAEMERS W H . Which graphs are determined by their spectrum?[J]. Linear Algebra and Its Applications, 2003, 373, 241- 272.
doi: 10.1016/S0024-3795(03)00483-X
2 CVETKOVIC D M , DOOB M , SACHS H . Spectra of graphs, 87: theory and application[M]. New York: Academic Press, 1997.
3 WANG W , LI F , LU H L , et al. Graphs determined by their generalized characteristic polynomials[J]. Linear Algebra and Its Applications, 2011, 434 (5): 1378- 1387.
doi: 10.1016/j.laa.2010.11.024
4 WANG W , MAO L H , LU H L . On bi-regular graphs determined by their generalized characteristic polynomials[J]. Linear Algebra and Its Applications, 2013, 438 (7): 3076- 3084.
doi: 10.1016/j.laa.2012.12.006
5 WANG Wei , XU Chengxian . An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra[J]. Linear Algebra and Its Applications, 2006, 418 (1): 62- 74.
doi: 10.1016/j.laa.2006.01.016
6 WANG W . Generalized spectral characterization of graphs revisited[J]. The Electronic Journal of Combinatorics, 2013, 20 (4): 823- 840.
7 KIM D , KIM H K , LEE J . Generalized characteristic polynomials of graph bundles[J]. Linear Algebra and Its Applications, 2008, 429 (4): 688- 697.
doi: 10.1016/j.laa.2008.03.023
8 BROUWER A E , HAEMERS W H . Spectra of graphs[M]. New York: Springer, 2011.
9 CHVÁTAL V , HAMMER P L . Aggregation of inequalities in integer programming[M]. Amsterdam: Elsevier, 1977: 145- 162.
10 HENDERSON P B , ZALCSTEIN Y . A graph-theoretic characterization of the PV class of synchronizing primitives[J]. SIAM Journal on Computing, 1977, 6 (1): 88- 108.
doi: 10.1137/0206008
11 HAGBERG A , SWART P J , SCHULT D A . Designing threshold networks with given structural and dynamical properties[J]. Physical Review E, 2006, 74 (5): 056116.
doi: 10.1103/PhysRevE.74.056116
12 BANERJEE A , MEHATARI R . On the normalized spectrum of threshold graphs[J]. Linear Algebra and Its Applications, 2017, 530, 288- 304.
doi: 10.1016/j.laa.2017.05.007
13 BAPAT R B . On the adjacency matrix of a threshold graph[J]. Linear Algebra and Its Applications, 2013, 439 (10): 3008- 3015.
doi: 10.1016/j.laa.2013.08.007
14 BAPAT R B . Laplacian eigenvalues of threshold graphs[M]. London: Springer, 2014: 145- 155.
15 HAMMER P L , KELMANS A K . Laplacian spectra and spanning trees of threshold graphs[J]. Discrete Applied Mathematics, 1996, 65 (1/3): 255- 273.
16 JACOBS D P , TREVISAN V , TURA F . Computing the characteristic polynomial of threshold graphs[J]. Journal of Graph Algorithms and Applications, 2014, 18 (5): 709- 719.
doi: 10.7155/jgaa.00342
17 MAHADEV N V , PELED U N . Threshold graphs and related topics[M]. Amsterdam: Elsevier, 1995.
18 LIU Fenjin , SIEMONS J , WANG Wei . New families of graphs determined by their generalized spectrum[J]. Discrete Mathematics, 2019, 342 (4): 1108- 1112.
doi: 10.1016/j.disc.2018.12.020
19 唐达. 三对角矩阵计算[J]. 高等学校计算数学学报, 1997, (2): 97- 104.
TANG Da . Tridiagonal matrix calculus[J]. Journal of Computational Mathematics in Colleges and Universities, 1997, (2): 97- 104.
20 刘长河, 汪元伦, 刘世祥. 用解线性方程组方法求三对角矩阵的逆及其应用[J]. 北京建筑工程学院学报, 2005, 21 (3): 59- 62.
doi: 10.3969/j.issn.1004-6011.2005.03.015
LIU Changhe , WANG Yuanlun , LIU Shixiang . Find the inverse matrix of tridiagonal matrix by solving systems of linear algebraic equations[J]. Journal of Beijing Institute of Civil Engineering and Architecture, 2005, 21 (3): 59- 62.
doi: 10.3969/j.issn.1004-6011.2005.03.015
21 ZHANG F Z . The Schur complement and its applications[M]. New York: Springer Science, 2005.
[1] 杨影,李沐春,张友. 剖分Q-邻接冠图的广义特征多项式及其应用[J]. 《山东大学学报(理学版)》, 2021, 56(7): 65-72.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 董爱君 李国君 邹青松. 含相邻三角形的平面图的列表边和列表全染色[J]. J4, 2009, 44(10): 17 -20 .
[2] 刘天宝,李宝宗,彭艳芬 . 有机物对沙癙幼虫麻醉活性的构效关系研究[J]. J4, 2006, 41(6): 129 -131 .
[3] 刘倩辉1,裴海燕1,2,*,胡文容1,2,解军3. 南四湖浮游植物种群构成特征及季节变化[J]. J4, 2010, 45(5): 12 -18 .
[4] 王 涛 . Post-Gamma算子关于导数为局部有界函数的点态逼近估计[J]. J4, 2007, 42(4): 75 -78 .
[5] 杨世洲1,宋雪梅2. 相对于幺半群的拟-MCCOY环[J]. J4, 2010, 45(8): 47 -52 .
[6] 范小莉,刘伯燕,梁玉,刘建,房用,孟振农. 南四湖湿地植被构成及分布分析[J]. 山东大学学报（理学版）, 2016, 51(7): 131 -136 .
[7] 李宇溪,王恺璇,林慕清,周福才. 基于匿名广播加密的P2P社交网络隐私保护系统[J]. 山东大学学报（理学版）, 2016, 51(9): 84 -91 .
[8] 刘甲国 . 高阶的分数阶的粘弹性材料本构模型的复模量与复柔量[J]. J4, 2008, 43(4): 85 -88 .
[9] 雷雪萍. 几乎C-倾斜模[J]. J4, 2011, 46(2): 101 -104 .
[10] 许兰图 . 非线性双曲[J]. J4, 2006, 41(4): 20 -24 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发