JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (11): 165-174.doi: 10.6040/j.issn.1671-9352.0.2022.062

Previous Articles    

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)

340

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

CLC Number: 

  • O157.5

Fig.1

Constructing a family of graphs"

Table 1

ΦΓ(λ, t) when m=1, 2, 3, 4"

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)$

Fig.2

Graphs G0 and H0"

Fig.3

Graphs Gi and 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] YANG Ying, LI Mu-chun, ZHANG You. Generalized characteristic polynomial of subdivision Q-neighbourhood corona graphs and its application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(7): 65-72.
[2] GAO Rui-mei, CHU Ying. Freeness of arrangements between the Weyl arrangements of types An-1 and Bn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 70-75.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] DONG Ai-Jun, LI Guo-Jun, JU Jing-Song. List edge and list total colorings of planar graphs with adjacent triangles[J]. J4, 2009, 44(10): 17 -20 .
[2] LIU Tian-bao,LI Zong-bao,PENG yan-fen, . Relationships between the anesthetic activities for Arenicola larva and the structures of organic molecules[J]. J4, 2006, 41(6): 129 -131 .
[3] LIU Qian-hui1, PEI Hai-yan1, 2,*, HU Wen-rong1,2, XIE Jun3. Population characteristics and seasonal variations of  phytoplankton in Nansi Lake[J]. J4, 2010, 45(5): 12 -18 .
[4] WANG Tao . Pointwise approximation of Post-Gamma operators for functions with locally bounded derivatives[J]. J4, 2007, 42(4): 75 -78 .
[5] YANG Shi-zhou1, SONG Xue-mei2. Quasi-McCoy rings relative to a monoid[J]. J4, 2010, 45(8): 47 -52 .
[6] FAN Xiao-li, LIU Bo-yan, LIANG Yu, LIU Jian, FANG Yong, MENG Zhen-nong. Analysis and distribution of wetland vegetation of Nansi Lake, China[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(7): 131 -136 .
[7] LI Yu-xi, WANG Kai-xuan, LIN Mu-qing, ZHOU Fu-cai. A P2P network privacy protection system based on anonymous broadcast encryption scheme[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 84 -91 .
[8] LIU Jia-guo . The complex modulus and the complex compliance for higher-order fractional constitutive models of visco-elastic materials[J]. J4, 2008, 43(4): 85 -88 .
[9] LEI Xue-ping. Almost complete C-tilting modules[J]. J4, 2011, 46(2): 101 -104 .
[10] XU Tu-lan . A.D.I. Galerkin method for a nonlinear hyperbolic differential system[J]. J4, 2006, 41(4): 20 -24 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd