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

Previous Articles     Next Articles

Complete characterization of graphs with exactly two negative eigenvalues

Shuang WANG(),Fang DUAN*()   

  1. School of Mathematics Science, Xinjiang Normal University, Urumqi 830017, Xinjiang, China
  • Received:2021-12-28 Online:2023-11-20 Published:2023-11-07
  • Contact: Fang DUAN E-mail:61586369@qq.com;fangbing327@126.com

RichHTML

0

PDF (PC)

270

Abstract:

Let Γn be the set of graphs of order n such that each of them has exactly two negative eigenvalues. In this paper, we introduce 3 graph transformations. Furthermore, we find 8 specific graphs in Γn, each of them has nullity no more than two and we show that, in terms of the above three congruent transformations of graph, all the other graphs of Γn can be constructed from these 8 specific graphs. Hence we completely characterize the graphs with exactly two negative eigenvalues.

Key words: negative inertia index, positive inertia index, nullity, congruent transformation

CLC Number: 

  • O157.5

Fig.1

Graphs C6 and H1-H9"

Fig.2

Graphs P4, P5, C5 and G1-G3"

Fig.3

Graphs H10-H15"

1 FAN Yizheng , QIAN Keshi . On the nullity of bipartite graphs[J]. Linear Algebra & its Applications, 2009, 430, 2943- 2949.
2 MA Haicheng , YANG Wenhua , LI Shenggang . Positive and negative inertia index of a graph[J]. Linear Algebra & its Applications, 2013, 438, 331- 341.
3 OBOUDI M R . Bipartite graphs with at most six non-zero eigenvalues[J]. ARS Mathematica Contemporenea, 2016, 11, 315- 325.
doi: 10.26493/1855-3974.749.264
4 OBOUDI M R . Characterization of graphs with exactly two non-negative eigen-values[J]. ARS Mathematica Contemporenea, 2017, 12, 271- 286.
5 SMITH J H . Symmetry and multiple eigenvalues of graphs[J]. Glasnik Mat Ser Ⅲ, 1977, 12 (1): 3- 8.
6 DUAN Fang , HUANG Qiongxiang , HUANG Xueyi . On graphs with exactly two positive eigenvalues[J]. ARS Mathematica Contemporenea, 2019, 17, 319- 347.
doi: 10.26493/1855-3974.1516.58f
7 DUAN Fang , HUANG Qiongxiang , HUANG Xueyi , et al. A complete characterization of graphs with exactly two positive eigenvalues[J]. Advances in Applied Mathematics, 2023, 144, 102457.
doi: 10.1016/j.aam.2022.102457
8 TORGAŠEV A . Graphs with exactly two negative eigenvalues[J]. Math Nachr, 1985, 122, 135- 140.
doi: 10.1002/mana.19851220113
9 TORGAŠEV A . On graphs with a fixed number of negative eigenvalues[J]. Discrete Mathematics, 1985, 57, 311- 317.
doi: 10.1016/0012-365X(85)90184-0
10 CVETKOVIĆD , DOOB M , SACH H . Spectra of graphs: theory and application[M]. New York: Academic Press, 1980: 81- 103.
[1] YANG Chen, MA Hai-cheng. Positive and negative inertia indexes and nullity of two special kinds of tricyclic graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 32-37.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
[2] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
[3] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[4] SUN Xiao-ting1, JIN Lan2*. Application of DOSY in oligosaccharide mixture analysis[J]. J4, 2013, 48(1): 43 -45 .
[5] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[6] YANG Lun, XU Zheng-gang, WANG Hui*, CHEN Qi-mei, CHEN Wei, HU Yan-xia, SHI Yuan, ZHU Hong-lei, ZENG Yong-qing*. Silence of PID1 gene expression using RNA interference in C2C12 cell line[J]. J4, 2013, 48(1): 36 -42 .
[7] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[8] YANG Ying, JIANG Long*, SUO Xin-li. Choquet integral representation of premium functional and related properties on capacity space[J]. J4, 2013, 48(1): 78 -82 .
[9] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[10] DONG Wei-wei. A new method of DEA efficiency ranking for decision making units with independent subsystems[J]. J4, 2013, 48(1): 89 -92 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd