最大虧格下界與上可嵌入圖類(lèi).pdf

1、本文主要研究了拓?fù)鋱D論的一個(gè)重要分支-圖的最大虧格問(wèn)題，得到了兩類(lèi)上可嵌入圖類(lèi)，以及一類(lèi)圖的最大虧格下界．具體如下： (1)用NG(u)表示一個(gè)圖G中任意點(diǎn)u的鄰域集，目前利用圖的鄰域性質(zhì)來(lái)研究圖的上可嵌入的結(jié)果甚少，結(jié)合圖G的鄰域條件，本文給出了兩類(lèi)上可嵌入圖，豐富了文獻(xiàn)[1-4]關(guān)于圖上可嵌入性的結(jié)果，并推廣了文獻(xiàn)[5]的一個(gè)結(jié)果． (2)圖G的頂點(diǎn)Pn-劃分是指：圖G的一個(gè)頂點(diǎn)劃分{V1，V2,…，Vs}，滿(mǎn)足每個(gè)

2、導(dǎo)出子圖G[Vi](1≤i≤s)為多重完全n部圖，本文結(jié)合圖的頂點(diǎn)Pn-劃分n≥3)、點(diǎn)度等條件，確定了一類(lèi)上可嵌入圖類(lèi)，從而豐富了已有這方面的結(jié)果(見(jiàn)文獻(xiàn)[6-10])． (3)圖G的頂點(diǎn)W-劃分是指：圖G的一個(gè)頂點(diǎn)劃分{V1，V2，…，V3}，滿(mǎn)足每個(gè)導(dǎo)出子圖G[Vi](1≤i≤s)都包含輪為生成子圖，結(jié)合W-劃分，給出了一個(gè)最大虧格比較好的下界，對(duì)于某些圖類(lèi)，該界比文獻(xiàn)[11]的界更好． 在文章最后部分，提出了幾個(gè)