逆度和图的性质

doi:10.3969/j.issn.0253-2778.2020.06.019

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (6): 852-859.DOI: 10.3969/j.issn.0253-2778.2020.06.019

逆度和图的性质

蔡改香，梅培林，余桂东

1.安庆师范大学数理学院，安徽安庆 246133;2.合肥幼儿师范高等专科学校公共教学部，安徽合肥 230013

收稿日期:2020-03-31 修回日期:2020-06-10 接受日期:2020-06-10 出版日期:2020-06-30 发布日期:2020-06-10

Inverse degree and properties of graphs

CAI Gaixiang, MEI Peilin, YU Guidong,2

Received:2020-03-31 Revised:2020-06-10 Accepted:2020-06-10 Online:2020-06-30 Published:2020-06-10
Contact: YU Guidong
About author:CAI Gaixiang, female, born in 1981, master/associate Prof. Research field: Graph theory. E-mail: caigaixiang@qq.com
Supported by:
Supported by the Natural Science Foundation of China (11871077), the NSF of Anhui Province (1808085MA04), the NSF of Department of Education of Anhui Province (KJ2017A362).

摘要/Abstract

摘要： 设G=(V(G),E(G))是n个顶点m条边的简单图.无孤立点的图G的逆度定义为ID(G)=∑vi∈V(G)1d(vi)，其中，d(vi)表示顶点vi的度.首先用逆度刻画了连通图分别是k-哈密尔顿、k-边哈密尔顿、k-路覆盖、哈密尔顿连通、k-连通、2-边连通和β-亏损的充分条件.其次用逆度给出了连通图的独立数小于等于整数k的充分条件.最后用逆度给出了连通的平衡二部图是哈密尔顿图的一个充分条件.

关键词: 逆度, 度序列, 图的性质

Abstract: Let G=(V(G), E(G)) be a simple graph

Key words: inverse degree, degree sequence, graph properties

中图分类号:

O157.5

蔡改香，梅培林，余桂东. 逆度和图的性质[J]. 中国科学技术大学学报, 2020, 50(6): 852-859.

参考文献

［1］ XU K, LIU M, DAS K C, et al. A survey on graphs extremal with respect to distance based topological indices[J]. MATCH Commun Math Comput Chem, 2014, 71: 461-508.
[2] GUTMAN I. Degree-based topological indices[J]. Croat Chem Acta, 2013, 86: 351-361.
[3] DAS K C, GUTMAN I, NADJAFIARANI M J. Relations between distance based and degree based topological indices[J]. Appl Math Comput, 2015, 270: 142-147.
[4] FAJTLOWICZ S. On conjectures of Graffiti II[J]. Congr Numer, 1987, 60:189-197.
[5] ZHANG Z, ZHANG J, LU X. The relation of matching with inverse degree of a graph[J]. Discrete Math, 2005, 301: 243-246.
[6] HU Y, LI X, XU T. Connected (n; m) graphs with minimum and maximum zeroth-order Randic＇ index[J]. Discrete Appl Math, 2007, 155: 1044-1054.
[7] DANKELMANN P, HELLWIG A, VOLKMANN L. Inverse degree and edge-connectivity[J]. Discrete Math, 2009, 309: 2943-2947.
[8] MUKWEMBI S. On diameter and inverse degree of a graph[J]. Discrete Math, 2010, 310: 940-946.
[9] LI X, SHI Y. On the diameter and inverse degree[J]. Ars Combin, 2011, 101: 481- 487.
[10] CHEN X, FUJITA S. On diameter and inverse degree of chemical graphs[J]. Appl Anal Discrete Math, 2013, 7: 83-93.
[11] XU K, DAS K C. Some extremal graphs with respect to inverse degree[J]. Discrete Appl Math, 2016, 203: 171-183.
[12] DAS K C, XU K, WANG J. On inverse degree and topological indices of graphs[J]. Filomat, 2016, 30: 2111-2120.
[13] DAS K C, BALACHANDRAN S, GUTMAN I. Inverse degree, Randic＇ index and harmonic index of graphs[J]. Appl Anal Discrete Math, 2017, 11(2): 304-313.
[14] ELUMALAI S, HOSAMANI S M, MANSOUR T, et al. More on inverse degree and topological indices of graphs[J]. Filomat, 2018, 32(1): 165-178.

[15] CHVTAL V. On Hamiltons ideals[J]. J Combin Theory Ser B, 1972, 12: 163-168.
[16] KRONK H V. A note on k-path Hamiltonian graphs[J]. J Combin Theory, 1969, 7: 104-106.
[17] BONDY J A , CHVTAL V. A method in graph theory[J]. Discrete Math, 1976, 15: 111-135.
[18] YU G D, YE M L, CAI G X, et al. Signless Laplacian spectral conditions for Hamiltonicity of graphs[J]. Journal of Applied Mathematics, 2014, 2014: Article ID 282053.
[19] BONDY J A. Properties of graphs with constraints on degrees[J]. Studia Sci Math Hungar, 1969, 4: 473-475.
[20] BAUER D, HAKIMI S L, KAHL N, et al. Sufficient degree conditions for k-edge-connectedness of a graph[J]. Networks, 2009, 54: 95-98.
[21] LAS VERGNAS M. Problèmes de couplages et problèmes Hamiltoniens en théorie des graphes[D]. Paris: Université Pierre-et-Marie-Curie, 1972.

[22] BAUER D, BROERSMA H J, VAN DEN HEUVEL J, et al. Best monotone degree conditions for graph properties: A survey[J]. Graphs Combin, 2015, 31: 1-22.
[23] BERGE C. Graphs and Hypergraphs[M]. Amsterdam: North-Holland, 1973.
[24] FENG L, ZHANG P, LIU H, et al. Spectral conditions for some graphical properties[J]. Linear Algebra and Its Applications, 2017, 524: 182-198.

()
()

[1]	李心田, 刘世平. Amply regular图的林-陆-丘曲率和直径[J]. 中国科学技术大学学报, 2021, 51(12): 889-893.
[2]	火清羿. 染色数为5和6的图中的圈长[J]. 中国科学技术大学学报, 2021, 51(5): 374-381.
[3]	剧宏娟，雷英杰. 三圈图和四圈图的最大无符号拉普拉斯分离度[J]. 中国科学技术大学学报, 2020, 50(4): 402-408.
[4]	蔡学鹏，杨伟. 折叠交叉立方体的2-外边连通度[J]. 中国科学技术大学学报, 2020, 50(2): 94-99.
[5]	王礼想，余桂东，徐弈. 图的哈密尔顿连通性和从任意点出发都可迹的充分条件[J]. 中国科学技术大学学报, 2020, 50(2): 100-105.
[6]	鲁学星. 顶点偏序集上的平面序[J]. 中国科学技术大学学报, 2018, 48(11): 902-905.
[7]	梁勇，裴利丹，胡夫涛，侯新民. 笛卡尔乘积和直积图的全{k}控制划分数[J]. 中国科学技术大学学报, 2018, 48(8): 605-611.
[8]	洪振木，福克曼·鲁茨，徐俊明. 有向图是极大连通的和超连通的充分条件[J]. 中国科学技术大学学报, 2018, 48(8): 612-617.

逆度和图的性质

Inverse degree and properties of graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价