可迹图和哈密顿图的谱充分条件研究
发布时间：2019-01-03 07:22
【摘要】：图谱理论是图论与组合矩阵论中的一个重要课题.判断一个给定图是否是可迹的或哈密顿的是NP-完全问题,给出简洁可用的谱充分条件是非常有意义的.下面我们将给出可迹图和哈密顿图的谱充分条件.·首先介绍了图谱理论的一些历史与背景以及本论文所研究问题的现状和意义.其次介绍了本论文用到的一些重要的概念和符号.最后简要介绍了本论文所做的主要工作.·对于一个连通图是否是可迹的或哈密顿的,本论文基于此图和相应补图的Wiener指数进行讨论给出了充分条件,改正和扩展了 Yang[45]的结果.进一步地,对于连通二部图也给出Wiener指数充分条件.最后,对于连通图和连通二部图给出了距离谱半径充分条件.·对于一个连通图是否是可迹的或哈密顿的,本论文基于此图和相应补图的Harary指数给出了充分条件,改正和扩展了 Hua和Wang[18]的结果.进一步地,对于连通二部图也给出了 Harary指数充分条件.最后,对于连通图和连通二部图给出了 Harary谱半径充分条件.
[Abstract]:Atlas theory is an important subject in graph theory and combinatorial matrix theory. To determine whether a given graph is traceable or Hamiltonian is a NP- complete problem, it is very meaningful to give a concise and usable sufficient condition of spectrum. Next, we give the spectral sufficient conditions of trace graph and Hamiltonian graph. Firstly, we introduce some history and background of graph theory and the present situation and significance of the problems studied in this paper. Secondly, some important concepts and symbols used in this paper are introduced. Finally, the main work of this paper is briefly introduced. For whether a connected graph is traceable or Hamiltonian, the sufficient conditions are given based on the discussion of the Wiener exponent of the graph and the corresponding complement graph. The result of Yang [45] is corrected and extended. Furthermore, a sufficient condition of Wiener exponent is given for connected bipartite graphs. Finally, the sufficient conditions of distance spectral radius for connected graphs and connected bipartite graphs are given. For whether a connected graph is traceable or Hamiltonian, this paper gives sufficient conditions based on this graph and the Harary exponent of the corresponding complement graph. The results of Hua and Wang [18] are corrected and extended. Furthermore, a sufficient condition of Harary exponent is given for connected bipartite graphs. Finally, the sufficient conditions of Harary spectral radius are given for connected graphs and connected bipartite graphs.
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
本文编号：2399060
[Abstract]:Atlas theory is an important subject in graph theory and combinatorial matrix theory. To determine whether a given graph is traceable or Hamiltonian is a NP- complete problem, it is very meaningful to give a concise and usable sufficient condition of spectrum. Next, we give the spectral sufficient conditions of trace graph and Hamiltonian graph. Firstly, we introduce some history and background of graph theory and the present situation and significance of the problems studied in this paper. Secondly, some important concepts and symbols used in this paper are introduced. Finally, the main work of this paper is briefly introduced. For whether a connected graph is traceable or Hamiltonian, the sufficient conditions are given based on the discussion of the Wiener exponent of the graph and the corresponding complement graph. The result of Yang [45] is corrected and extended. Furthermore, a sufficient condition of Wiener exponent is given for connected bipartite graphs. Finally, the sufficient conditions of distance spectral radius for connected graphs and connected bipartite graphs are given. For whether a connected graph is traceable or Hamiltonian, this paper gives sufficient conditions based on this graph and the Harary exponent of the corresponding complement graph. The results of Hua and Wang [18] are corrected and extended. Furthermore, a sufficient condition of Harary exponent is given for connected bipartite graphs. Finally, the sufficient conditions of Harary spectral radius are given for connected graphs and connected bipartite graphs.
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【参考文献】
相关期刊论文 前1条
1 刘中柱;林思思;杨国强;;图的哈密尔顿性及其距离谱半径(英文)[J];惠州学院学报;2013年06期
，本文编号：2399060
本文链接：https://www.wllwen.com/kejilunwen/yysx/2399060.html
