【摘要】：圖譜理論是圖論與組合矩陣論中的一個重要課題.判斷一個給定圖是否是可跡的或哈密頓的是NP-完全問題,給出簡潔可用的譜充分條件是非常有意義的.下面我們將給出可跡圖和哈密頓圖的譜充分條件.·首先介紹了圖譜理論的一些歷史與背景以及本論文所研究問題的現(xiàn)狀和意義.其次介紹了本論文用到的一些重要的概念和符號.最后簡要介紹了本論文所做的主要工作.·對于一個連通圖是否是可跡的或哈密頓的,本論文基于此圖和相應補圖的Wiener指數(shù)進行討論給出了充分條件,改正和擴展了 Yang[45]的結果.進一步地,對于連通二部圖也給出Wiener指數(shù)充分條件.最后,對于連通圖和連通二部圖給出了距離譜半徑充分條件.·對于一個連通圖是否是可跡的或哈密頓的,本論文基于此圖和相應補圖的Harary指數(shù)給出了充分條件,改正和擴展了 Hua和Wang[18]的結果.進一步地,對于連通二部圖也給出了 Harary指數(shù)充分條件.最后,對于連通圖和連通二部圖給出了 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

【參考文獻】

相關期刊論文 前1條

1 劉中柱;林思思;楊國強;;圖的哈密爾頓性及其距離譜半徑(英文)[J];惠州學院學報;2013年06期

，

本文編號：2399060