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

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

•   • 上一篇    下一篇

基于完全图构造的两类整图

王力工1(),郁志明1,*(),周枫2,陶丽杰1,邢露淇3   

  1. 1. 西北工业大学数学与统计学院, 陕西 西安 710129
    2. 西北工业大学教育实验学院, 陕西 西安 710129
    3. 西北工业大学管理学院, 陕西 西安 710129
  • 收稿日期:2022-02-07 出版日期:2023-11-20 发布日期:2023-11-07
  • 通讯作者: 郁志明 E-mail:lgwang@nwpu.edu.cn;yzm2020303246@mail.nwpu.edu.cn
  • 作者简介:王力工(1968—)，男，教授，研究方向为图论及其应用. E-mail：lgwang@nwpu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(11871398);陕西省大学生创新创业训练计划资助项目(S202110699704)

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)

437

摘要：

定义了两类新图q * Kn与K1, m ·(q * Kn)。利用粘接图的特征多项式性质得到了这两类图的特征多项式，并刻画了这两类图为整图的含参数充要条件，进而也给出了它们为整图的一些充分条件。

关键词: 整图, 邻接矩阵, 特征多项式, 完全图

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

中图分类号: 

  • O157.5

表1

推论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] 常乐,魏宗田. 基于邻域连通度优化的图的N[S]-T重构[J]. 《山东大学学报(理学版)》, 2023, 58(6): 40-45, 76.
[2] 王冉冉,文飞,张树成. 一类图的广义特征多项式[J]. 《山东大学学报(理学版)》, 2023, 58(11): 165-174.
[3] 索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[4] 张苗,强晶晶,高瑞梅. Dn型通有构形的特征多项式[J]. 《山东大学学报(理学版)》, 2022, 57(10): 106-110.
[5] 杨影,李沐春,张友. 剖分Q-邻接冠图的广义特征多项式及其应用[J]. 《山东大学学报(理学版)》, 2021, 56(7): 65-72.
[6] 张生桂,陈祥恩. 近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(5): 23-25.
[7] 贾淑香,邓波,冶成福,付凤,陈辉龙. 图的Resolvent Estrada指标的上(下)界刻画[J]. 《山东大学学报(理学版)》, 2020, 55(4): 92-96.
[8] 高瑞梅,李喆. 简单相连多边形对应的图构形的特征多项式[J]. 山东大学学报（理学版）, 2016, 51(10): 72-77.
[9] 高瑞梅1,裴东河2. 构形的特征多项式和超可解性的算法[J]. 山东大学学报（理学版）, 2014, 49(2): 51-57.
[10] 卢世芳1,卫良2,赵海兴2. 完全3-部图的无符号Laplace谱[J]. J4, 2012, 47(12): 41-46.
[11] 曹海松，伍俊良 . 矩阵特征值在椭圆形区域上的估计[J]. J4, 2012, 47(10): 49-53.
[12] 袁秀华. 完全图的全符号控制数[J]. J4, 2010, 45(8): 43-46.
[13] 张爽,裴东河,高瑞梅. 广义p-通有中心平行构形[J]. J4, 2010, 45(8): 32-35.
[14] 崔秀鹏 裴东河 高瑞梅. S2球构形的分类及一类特殊球构形的特征多项式[J]. J4, 2010, 45(2): 10-13.
[15] 袁秀华. 图的符号边全控制数[J]. J4, 2009, 44(8): 21-24.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 唐风琴1,白建明2. 一类带有广义负上限相依索赔额的风险过程大偏差[J]. J4, 2013, 48(1): 100 -106 .
[2] 王　瑶,刘　建,王仁卿,* . 阿利效应及其对生物入侵和自然保护中小种群管理的启示[J]. J4, 2007, 42(1): 76 -82 .
[3] 刘保仓,史开泉 . S-粗集的信度特征[J]. J4, 2006, 41(5): 26 -29 .
[4] 郭 会,林 超 . 对流占优Sobolev方程的最小二乘特征混合有限元方法[J]. J4, 2008, 43(9): 45 -50 .
[5] 王志刚 秦新强 党发宁 苏李君. 楔形基无网格法解的存在惟一性[J]. J4, 2010, 45(2): 44 -49 .
[6] 石松1,王明文1,涂伟2,何世柱1. 基于Markov网络团的信息检索扩展模型[J]. J4, 2011, 46(5): 54 -57 .
[7] 韩宗贤,孙渭滨. 一类推广的Bernstein-Kantorovich算子在Bα空间中加权逼近的等价定理[J]. J4, 2011, 46(4): 93 -97 .
[8] 王锦玲,刘宗成 . 主控生成器[J]. J4, 2008, 43(1): 81 -87 .
[9] . 求解变分不等式的修正三步迭代法[J]. J4, 2009, 44(6): 69 -74 .
[10] 曹慧 张艳 尹永田 马金刚. 基于Flex+J2ee技术的针灸穴位信息服务系统[J]. J4, 2009, 44(9): 43 -46 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发