【摘要】：圖譜理論是圖論與組合矩陣論中的一個(gè)重要課題.判斷一個(gè)給定圖是否是可跡的或哈密頓的是NP-完全問(wèn)題,給出簡(jiǎn)潔可用的譜充分條件是非常有意義的.下面我們將給出可跡圖和哈密頓圖的譜充分條件.·首先介紹了圖譜理論的一些歷史與背景以及本論文所研究問(wèn)題的現(xiàn)狀和意義.其次介紹了本論文用到的一些重要的概念和符號(hào).最后簡(jiǎn)要介紹了本論文所做的主要工作.·對(duì)于一個(gè)連通圖是否是可跡的或哈密頓的,本論文基于此圖和相應(yīng)補(bǔ)圖的Wiener指數(shù)進(jìn)行討論給出了充分條件,改正和擴(kuò)展了 Yang[45]的結(jié)果.進(jìn)一步地,對(duì)于連通二部圖也給出Wiener指數(shù)充分條件.最后,對(duì)于連通圖和連通二部圖給出了距離譜半徑充分條件.·對(duì)于一個(gè)連通圖是否是可跡的或哈密頓的,本論文基于此圖和相應(yīng)補(bǔ)圖的Harary指數(shù)給出了充分條件,改正和擴(kuò)展了 Hua和Wang[18]的結(jié)果.進(jìn)一步地,對(duì)于連通二部圖也給出了 Harary指數(shù)充分條件.最后,對(duì)于連通圖和連通二部圖給出了 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.
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

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

，

本文編號(hào)：2399060