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

Previous Articles     Next Articles

Two kinds of integral graphs based on complete graphs

Ligong WANG1(),Zhiming YU1,*(),Feng ZHOU2,Lijie TAO1,Luqi XING3   

  1. 1. School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an 710129, Shaanxi, China
    2. Honors College, Northwestern Polytechnical University, Xi'an 710129, Shaanxi, China
    3. School of Management, Northwestern Polytechnical University, Xi'an 710129, Shaanxi, China
  • Received:2022-02-07 Online:2023-11-20 Published:2023-11-07
  • Contact: Zhiming YU E-mail:lgwang@nwpu.edu.cn;yzm2020303246@mail.nwpu.edu.cn

RichHTML

0

PDF (PC)

216

Abstract:

Two kinds of new graphs q * Kn and K1, m·(q * Kn) are defined. We obtain their characteristic polynomials by using the properties of characteristic polynomials of coalescence of graphs. We also characterize sufficient and necessary conditions with parameters for these graphs to be integral. Furthermore, some sufficient conditions for these graphs to be integral are presented.

Key words: integral graph, adjacency matrix, characteristic polynomial, complete graph

CLC Number: 

  • O157.5

Table 1

Parametric solutions in Corollary 3.2"

m n q a b c m n q a b c
5 5 2 5 1 -3 10 10 2 10 2 -4
10 4 3 5 1 -4 28 7 6 10 2 -7
28 4 9 8 1 -7 60 5 7 10 2 -9
21 5 10 9 1 -7 54 6 3 9 3 -8
33 5 16 11 1 -9 33 9 4 11 3 -7
55 4 18 11 1 -10 44 8 5 11 3 -8
20 5 2 6 2 -5 88 7 3 11 4 -10
28 5 3 7 2 -6 45 9 1 9 5 -7
16 7 3 8 2 -5 60 8 1 9 5 -8
24 6 4 8 2 -6 55 10 2 11 5 -8
1 HARARY F, SCHWENK A J. Which graphs have integral spectra[M]//Graphs and Combinatorics. Berlin: Springer, 1973: 18-22.
2 李学良, 林国宁. 关于整树问题[J]. 科学通报, 1987, 32 (11): 813- 816.
LI Xueliang , LIN Guoning . On integral trees problems[J]. Kexue Tongbao (Chinese), 1987, 32 (11): 813- 816.
3 BALIŃSKA K , CVETKOVIĆ D , RADOSAVLJEVIĆ Z , et al. A survey on integral graphs[J]. Publikacije Elektrotehnickog Fakulteta-Serija: Matematika, 2002, (13): 42- 65.
4 WANG Ligong. Integral trees and integral graphs[D]. Enschede: University of Twente, 2005.
5 CVETKOVIĆ D, ROWLINSON P, SIMIĆ S. An introduction to the theory of graph spectra[M]//New York: Cambridge University Press, 2010.
6 GHORBANI E , MOHAMMADIAN A , TAYFEH-REZAIE B . Integral trees of odd diameters[J]. Journal of Graph Theory, 2012, 70 (3): 332- 338.
doi: 10.1002/jgt.20619
7 WANG Ligong , WANG Qi , HUO Bofeng . Integral trees with diameter four[J]. Applied Mathematics and Computation, 2016, (282): 53- 64.
8 GHORBANI E , MOHAMMADIAN A , TAYFEH-REZAIE B . Integral trees with given nullity[J]. Discrete Mathematics, 2016, 339 (1): 157- 164.
doi: 10.1016/j.disc.2015.08.007
9 WANG Ligong , LI Xueliang , ZHANG Shenggui . Construction of integral graphs[J]. Applied Mathematics-A Journal of Chinese Universities, 2000, 15 (3): 239- 246.
doi: 10.1007/s11766-000-0046-z
10 BAPAT R B , KARIMI M . Integral complete multipartite graphs[J]. Linear Algebra and its Applications, 2018, 549, 1- 11.
doi: 10.1016/j.laa.2018.03.026
11 DE LIMA L S , MOHAMMADIAN A , OLIVEIRA C S . On integral graphs with at most two vertices of degree larger than two[J]. Linear Algebra and its Applications, 2020, 584, 164- 184.
doi: 10.1016/j.laa.2019.09.019
12 GORYAINOV S , KONSTANTINOVA E V , LI Honghai , et al. Integral graphs obtained by dual Seidel switching[J]. Linear Algebra and its Applications, 2020, 604, 476- 489.
doi: 10.1016/j.laa.2020.07.010
13 BRAGA R O , DEL-VECCHIO R R , RODRIGUES V M . Integral unicyclic graphs[J]. Linear Algebra and its Applications, 2021, 614, 281- 300.
doi: 10.1016/j.laa.2020.05.002
14 HUANG Jing , LI Shuchao . Integral and distance integral Cayley graphs over generalized dihedral groups[J]. Journal of Algebraic Combinatorics, 2021, 53 (4): 921- 943.
doi: 10.1007/s10801-020-00948-1
15 KONSTANTINOVA E V , LYTKINA D . Integral Cayley graphs over finite groups[J]. Algebra Colloquium, 2020, 27 (1): 131- 136.
doi: 10.1142/S1005386720000115
16 BAŠIĆ M . Characterization of strongly regular integral circulant graphs by spectral approach[J]. Applicable Analysis and Discrete Mathematics, 2022, 16 (2): 288- 306.
doi: 10.2298/AADM180713023B
17 CHENG Tao , FENG Lihua , LIU Weijun , et al. Distance powers of integral Cayley graphs over dihedral groups and dicyclic groups[J]. Linear and Multilinear Algebra, 2022, 70 (7): 1281- 1290.
doi: 10.1080/03081087.2020.1758609
18 LEPOVIĆ M . On integral graphs which belong to the class αGa∪βGb where Ga and Gbare two regular integral graphs[J]. Discrete Mathematics, 2023, 346 (5): 1- 11.
19 ARSIĆ B , CVETKOVIĆ D , SIMIĆ S K , et al. Graph spectral techniques in computer sciences[J]. Applicable Analysis and Discrete Mathematics, 2012, 6 (1): 1- 30.
doi: 10.2298/AADM111223025A
20 GODSIL C D , MCKAY B D . Constructing cospectral graphs[J]. Aequationes Mathematicae, 1982, 25 (1): 257- 268.
doi: 10.1007/BF02189621
21 BIGGS N . Algebraic graph theory[M]. New York: Cambridge University Press, 1993.
[1] Le CHANG,Zongtian WEI. Graph N[S]-T reconstruction based on neighbor connectivity optimization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 40-45, 76.
[2] WANG Ranran, WEN Fei, ZHANG Shucheng. On the generalized characteristic polynomial of a family of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 165-174.
[3] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[4] ZHANG Miao, QIANG Jing-jing, GAO Rui-mei. Characteristic polynomials for the generic arrangements of type Dn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 106-110.
[5] 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.
[6] ZHANG Sheng-gui, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total coloring and Ⅵ-total coloring of almost complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(5): 23-25.
[7] . The characteristic polynomials of the graphical arrangements corresponding to the simply-connected polygons [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 72-77.
[8] GAO Rui-mei1, PEI Dong-he2. The algorithms of characteristic polynomial and supersolvability#br#  of a hyperplane arrangement [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(2): 51-57.
[9] LU Shi-fang1, WEI Liang2, ZHAO Hai-xing2. On signless Laplace integral graphs of complete tripartite graphs [J]. J4, 2012, 47(12): 41-46.
[10] CAO Hai-song， WU Jun-liang. On localization of eigenvalues in elliptic region [J]. J4, 2012, 47(10): 49-53.
[11] YUAN Xiu-hua. The total signed domination number of complete graph [J]. J4, 2010, 45(8): 43-46.
[12] ZHANG Shuang, PEI Dong-he, GAO Rui-mei. Generalized p-generic center parallel arrangements [J]. J4, 2010, 45(8): 32-35.
[13] CUI Xiu-Peng, PEI Dong-He, GAO Rui-Mei. The classification of a sphere arrangement in S2andits characteristic polynomial [J]. J4, 2010, 45(2): 10-13.
[14] YUAN Xiu-Hua. Signed edge total domination numbers of graphs [J]. J4, 2009, 44(8): 21-24.
[15] LIU Hai-Yang, MA Cheng-Gang, WANG Zhi-Beng. Graham's conjecture on the product of the thorn graph [J]. J4, 2009, 44(8): 25-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] TANG Feng-qin1, BAI Jian-ming2. The precise large deviations for a risk model with extended negatively upper orthant dependent claim  sizes[J]. J4, 2013, 48(1): 100 -106 .
[2] QANG Yao,LIU Jian and WANG Ren-qing,* . Allee effect and its significance to small population management in nature reservation and biological invasions[J]. J4, 2007, 42(1): 76 -82 .
[3] LIU Bao-cang,SHI Kai-quan . Reliablity characteristics of Srough sets[J]. J4, 2006, 41(5): 26 -29 .
[4] GUO Hui,LIN Chao . A least-squares mixed finite element procedure with the method of
characteristics for convection-dominated Sobolev equations[J]. J4, 2008, 43(9): 45 -50 .
[5] WANG Zhi-Gang, QIN Xin-Qiang, DANG Fa-Ning, SU Li-Jun. The existence and uniqueness of the solution to meshless methodwith ridge basis functions[J]. J4, 2010, 45(2): 44 -49 .
[6] SHI Song1, WANG Ming-wen1, TU Wei2, HE Shi-zhu1. Extended information retrieval model based on the Markov network cliques[J]. J4, 2011, 46(5): 54 -57 .
[7] HAN Zong-xian, SUN Wei-bin. Equivalent theorem of weighted approximation for a kind of generalized Bernstein-Kantorovich operators in Bα spaces[J]. J4, 2011, 46(4): 93 -97 .
[8] WANG Jin-ling,LIU Zong-cheng . The main-controlled generator[J]. J4, 2008, 43(1): 81 -87 .
[9] . Modified threestep iterative method for solving variational inequalities[J]. J4, 2009, 44(6): 69 -74 .
[10] CAO Hui, ZHANG Yan, YIN Yong-Tian, MA Jin-Gang. An acupoint information system for acupuncture and moxibustionbased on Flex J2ee technology[J]. J4, 2009, 44(9): 43 -46 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd