（運(yùn)籌學(xué)與控制論專業(yè)論文）關(guān)于圖的上可嵌入性研究.pdf

摘要 自n o r d h a u s ，s t e w a r t 和w h i t e 1 】引進(jìn)最大虧格以來(lái)，圖的上可嵌入性 至今倍受人們的注意雖然x u o n g 2 ，l i u 3 】和n e b e s k y 4 】分別提供了不同 的確定圖的上可嵌入性的充要條件，但對(duì)于什么類型的圖是上可嵌入的 仍尚知不多 如果一個(gè)圖的最大虧格能夠取到最好的上界 z ( g ) 2 j ，則這個(gè)圖就是 上可嵌入的近些年來(lái)，許多圖論學(xué)者都在研究圖的上可嵌入性與圖的 各項(xiàng)參數(shù)之間的關(guān)系，并得到了一些上可嵌入圖類本文結(jié)合圖的圈中 頂點(diǎn)度，支配集，頂點(diǎn)a 劃分得到了幾類上可嵌入圖具體內(nèi)容如下 第一章和第二章，介紹了圖的上可嵌入理論的背景以及所需要掌握 的基本概念和定理 第三章，結(jié)合圈中頂點(diǎn)最大度，得到了兩類上可嵌入圖 第四章，結(jié)合圖的支配集，得到了兩類上可嵌入圖 第五章，結(jié)合圖的頂點(diǎn)a 劃分、頂點(diǎn)的度及其邊連通性等條件確定 了一類上可嵌入圖類，從而將已有這方面的結(jié)果作了較大的推廣，完整 地刻畫(huà)了這類圖的上可嵌入情況 在結(jié)語(yǔ)中，介紹了關(guān)于上可嵌入性理論的研究前景和作者今后的工 作 關(guān)鍵詞：上可嵌入；最大虧格；b e t t i 虧數(shù)；支配集；a 一劃分 a b s t r a c t s i n c et h ei n t r o d u c t o r yi n v e s t i g a t i o no fm a x i m u mg e n u sb yn o r d h a u s ，s t e w a r t ，a n d w h i t e 1 ，t h eu p p e re m b e d d a b i l i t yo fg r a p h sh a sb e e nd e v e l o p i n g8 0f a r a l t h o u g h x u o n g 2 ，l i u 3 】a n dn e b e s k y 4 h a v er e s p e c t i v e l yp r o v i d e dd i f f e r e n tn e c e s s a x ya n d s u f f i c i e n tc o n d i t i o n so nt h eu p p e re m b e d d a b i l i t yo f 口印1 1 j s ，w ek n o wl e s sa b o u tw h a t c l a s s e so fg r 印1 1 sa r eu p p e re m b e d d a b l e i ft h eu p p e rb o u n do nt h em a x i m u mg e n u so fag r a p hgc a l la r r i v ea tt h e b e s tv a l u e 壚( c ) 2 j ，t h e nw ec a l ls u c hag r a p hgi su p p e re m b e d d a b l e i nr e c e n t y e a r s ，m a n yg r a p h st h e o r ys c h o l a r sr e s e a r c ho nt h er e l a t i o n sb e t w e e np a r a m e t e r s a n dt h eu p p e re m b e d d a b i l i t yo fg r a p h s t h e yh a v ea t t a i n e dm a n yc l a s s e so fu p p e r e m b e d d a b l eg r 印h s i nt h i sp a p e rw ep r o v i d es o m en e wc l a s s e so fu p p e re m b e d d a b l e 伊a p h sb yc o m b i n i n gw i t ht h em a xd e g r e eo fv e t e xi nc y c l e ，t h ed o m i n a t ev e r t i c e s s e to fg r 印l l s ，a n dt h ec o n t i d i o n so fa p a r t i t i o n t h ed e t a i l sa r ea sf o l l o w s i nc h a p t e ro n ea n dt w o ，w ei n t r o d u c et h eb a c k g r o u n da n dr e q u i r e dk n o w l e d g e o ft h eu p p e re m b e d d a b i l i t yo fg r a p h s ，a n dg i v ep r i m a r yc o n c e p t i o n sa n dt h e o r e m s i nc h a p t e rt h r e e ，c o m b i n i n g 祈t ht h em a xd e g r e eo fv e t e xi nc y c l e ，w ea t t a i n t w oc l a s s e so fu p p e re m b e d d a b l eg r 印h 8 i nc h a p t e rf o u r ，c o m b i n i n gw i t ht h ed o m i n a t ev e r t i c e ss e to fg r a p l l 8 ，w ea t t a i n t w oc l a s s e so fu p p e re m b e d d a b l eg r a p h s i nc h a p t e rf i v e ，c o m b i n i n gw i t ha p a r t i t i o n ，d e g r e eo fv e r t e xa n de d g e - c o n n e c t i v i t y , w ea t t a i ns o m en e wc l a s s e so fu p p e re m b e d d a b l eg r a p h s t h u sw eg e n e r a l i z ef u r t h e r t h er e l a t i v er e s u l t s ，a n dc h a r a c t e r i z ee n t i r e l ys u c hu p p e re m b e d d a b l eg r 印h 8 i nt h ee n d ，w ei n t r o d u c et h er e s e a r c h i n gp r o s p e c to ft h eu p p e re m b e d d a b i l i t y 0 fg r 印l l sa n ds t a t ea u t h o r sn e x tw o r k k e yw o r d s ：u p p e re m b e d d a b l e ；m a x i m u mg e n u s ；b e t t id e f i c i e n c y ；t h ed o m i n a t e v e r t i c e ss e t ；a - p a r t i t i o n i i i 湖南師范大學(xué)學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn) 行研究所取得的研究成果除了文中特別加以標(biāo)注引用的內(nèi)容外，本論 文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)的成果作品對(duì)本文的研 究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明本人完全 意識(shí)到本聲明的法律后果由本人承擔(dān) 學(xué)位論文作者簽名：膨；篆蜂 仲多月d 日 i 湖南師范大學(xué)學(xué)位論文版權(quán)使用授權(quán)書(shū) 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意 學(xué)校保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論 文被查閱和借閱本人授權(quán)湖南師范大學(xué)可以將學(xué)位論文的全部或部分 內(nèi)容編人有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段 保存和匯編本學(xué)位論文 本學(xué)位論文屬于 1 、保密口，在年解密后適用本授權(quán)書(shū) 2 、不保密 ( 請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打q 、力) 作者彌侈1 螺 導(dǎo)師簽 石乃l 日腑雌知j f j 日 日期珈年6 月，護(hù)日 關(guān)于圖的上可嵌入性研究 1 引言 圖論是組合數(shù)學(xué)的一個(gè)重要組成部分，在最近的幾十年里，它已經(jīng) 發(fā)展成為數(shù)學(xué)的一個(gè)重要分支由于圖論本身的魅力和其在信息社會(huì)中 一些學(xué)科領(lǐng)域諸如計(jì)算機(jī)，運(yùn)籌學(xué)，系統(tǒng)工程以及物理學(xué)、電子學(xué)、化 學(xué)、通訊科學(xué)、生物遺傳學(xué)、社會(huì)學(xué)等學(xué)科都有廣泛應(yīng)用，因此，越來(lái)越 受到科學(xué)界尤其是數(shù)學(xué)界的重視和關(guān)注由于組合數(shù)學(xué)，代數(shù)學(xué)，拓?fù)鋵W(xué) 以及概率方法的結(jié)合，現(xiàn)代圖論除了傳統(tǒng)的研究領(lǐng)域外又?jǐn)U大到包括代 數(shù)圖論，拓?fù)鋱D論，以及隨機(jī)圖論等分支在內(nèi)的多個(gè)新的領(lǐng)域，促進(jìn)了 圖論的發(fā)展 拓?fù)鋱D論是目前國(guó)際上一個(gè)非?；钴S的圖論分支，將圖論與拓?fù)鋵W(xué) 理論結(jié)合起來(lái)，極大地豐富了圖論和拓?fù)鋵W(xué)本身的研究，其中對(duì)圖的拓 撲參數(shù)一最大虧格的研究又是一個(gè)十分重要的課題之一自從上世紀(jì)七 十年代初，由e n o r l d a u s ，b s t e w a r t 和a w h i t e 1 1 提出圖的最大虧格以來(lái)， 很多圖論學(xué)者都投身于這方面的研究，隨著對(duì)其研究的深入，它越來(lái)越 多地與其它數(shù)學(xué)分支相互交叉，相互影響，極大的促進(jìn)了虧格理論的發(fā) 展目前，關(guān)于圖的最大虧格的研究主要表現(xiàn)在如下幾個(gè)方面： ( 1 ) 特征結(jié)構(gòu) 上世紀(jì)七十年代末，n h x u o n g 2 1 借助于圖的支撐樹(shù)上的補(bǔ)圖，通過(guò) 引進(jìn)b e t t i 虧數(shù)，給出了圖的最大虧格的表示定理國(guó)內(nèi)劉彥佩教授【3 】3 通 過(guò)應(yīng)用確向樹(shù)理論方法，證明了一個(gè)圖是上可嵌入的當(dāng)且僅當(dāng)存在2 重 圖上的標(biāo)準(zhǔn)e u l e r 圈，給出了一些圖的嵌入的可約化模型，也構(gòu)造性地解決 了圖的不可定向最大虧格的存在性問(wèn)題上世紀(jì)八十年代初，l n e b e s k y 【4 】 用圖的去邊子圖給出了圖的另一個(gè)b e t t i 虧數(shù)的組合表達(dá)式由此，黃元 秋教授和劉彥佩教授【5 】研究了圖不是上可嵌入的充要條件 n h x u o n g ，j c h e n 和j l g r o 豁【6 】【7 】【8 】等人的工作表明對(duì)圖的最大虧格的研究往往可 以轉(zhuǎn)化為一個(gè)特殊的3 正則圖的情形黃元秋教授和劉彥佩教授 9 】證 1 碩士學(xué)位論文 明了一個(gè)孓正則圖的最大虧格等于其最大不可分離獨(dú)立數(shù)，在結(jié)構(gòu)上給 出3 - 正則圖上可嵌入的充要條件另外，黃元秋教授和劉彥佩教授【1 0 通過(guò)引進(jìn)圖的擴(kuò)張運(yùn)算，研究了擴(kuò)張運(yùn)算與圖的b e t t i 虧數(shù)之間的內(nèi)在聯(lián) 系，揭示了圖的最大虧格與圖的2 因子的某些聯(lián)系然而，在探求圖的 最大虧格的結(jié)構(gòu)特征上，仍有廣闊的前景 ( 2 ) 上可嵌入性 一個(gè)圖是上可嵌入的表明其最大虧格可取到最好的上界雖然在早 些年x u o n g 2 ，l i u 3 】和n e b e s k y 4 】分別提供了不同的確定圖的上可嵌入性 充要條件，但對(duì)于什么類型的圖是上可嵌入的尚知不多學(xué)者k u n d u 1 l 】 最早證明了所有垂邊連通圖是上可嵌入的，j u n g e r m a n 1 2 1 在他的論文中 證明了確實(shí)存在3 - 邊連通而非上可嵌入的圖于是這方面的研究就只需 討論什么樣的k ( k 3 ) 一邊連通圖是上可嵌入的目前，結(jié)合圖的其它參數(shù) 來(lái)討論圖的上可嵌入性已經(jīng)有了許多結(jié)果例如l n e b e s k y 1 3 1 4 1 5 1 證明 了半局部連通圖及2 局部連通圖均是上可嵌入的m s k o v i e r 1 6 ，h u a n g - l i n f u 和m i n - c h e nt s c a i 1 7 分別考慮直徑為2 和3 的圖的上可嵌入性 m s k o v i e r ，r n e d e a l 1 8 1 證明了一個(gè)圖嵌入曲面上使得每個(gè)面度的大小不 超過(guò)4 ，則該圖是上可嵌入的，并提出了一個(gè)放松條件到每個(gè)面度的大小 不超過(guò)5 的猜想前些年，黃元秋教授和劉彥佩教授 1 9 】證明了這個(gè)猜 想近期，國(guó)內(nèi)已有很多學(xué)者結(jié)合圖的點(diǎn)和邊連通性、直徑、半徑、圍 長(zhǎng)、頂點(diǎn)度、最小度、2 因子、獨(dú)立數(shù)、匹配數(shù)、頂點(diǎn)劃分等條件，得到 一些新的上可嵌入圖類這些結(jié)果可以參閱文獻(xiàn) 2 0 - 3 3 ( 3 ) 最大虧格的下界 判斷出一個(gè)圖是否是上可嵌入的，即圖的最大虧格是否能取到最好 的上界，有時(shí)候是不容易的于是，確定這個(gè)圖的最大虧格與其它參數(shù) 有關(guān)的比較好的下界成為一個(gè)引起眾多學(xué)者關(guān)注的問(wèn)題n h x u o n g 和 l n e b e s k y 考慮了最大虧格與圖的連通性的關(guān)系j c h e n 和j l g r o s s 給出 了與連通性有關(guān)的簡(jiǎn)單圖的最大虧格的下界估計(jì)式d a r c h d e a c o n 考慮了 2 關(guān)于圖的上可嵌入性研究 3 - 邊連通( 非簡(jiǎn)單) 圖的情形黃元秋教授推廣了上述工作，對(duì)任意k - 邊 連通( 非簡(jiǎn)單) 圖，給出了由圖的最小度所表達(dá)的圖的最大虧格的下界表 達(dá)式，證明了最小度趨向無(wú)窮大時(shí)，最大虧格趨近最好的上界最近，黃 元秋教授研究了圖的最大虧格與圖的余色數(shù)及團(tuán)的關(guān)系，利用h e a d w o o d 著色定理揭示了圖的最大虧格與圖的虧格之間的聯(lián)系這方面的文獻(xiàn)可 以參閱f 縱1 】 本文在以上所述學(xué)者工作的基礎(chǔ)上研究了圖的上可嵌入性，分別結(jié) 合圖的圈中頂點(diǎn)度，支配集，頂點(diǎn)a 劃分得到了幾類上可嵌入圖，豐富 了這方面的相關(guān)結(jié)果具體安排如下 第二章，2 1 介紹了本文所需的一些基本概念，2 2 列出了本文結(jié) 果證明過(guò)程中用到的幾個(gè)基本定理與事實(shí) 第三章，結(jié)合圈中頂點(diǎn)度，得到了兩類上可嵌入圖3 1 證明了一 般的參邊連通簡(jiǎn)單圖在其圈中頂點(diǎn)度滿足一定條件后，該圖就是一個(gè)上 可嵌入圖3 2 討論的則是2 - 邊連通的簡(jiǎn)單二部圖 第四章，結(jié)合圖的支配集，得到了兩類上可嵌入圖4 1 討論以輪 為支配集的上可嵌入圖，4 2 討論了以完全冬部圖為支配集的上可嵌入 圖 第五章，引入圖的頂點(diǎn)a 劃分，也同樣得到了幾類上可嵌入圖，并 推廣和深化了早先一些學(xué)者的結(jié)果 結(jié)語(yǔ)部分，介紹了關(guān)于上可嵌入性理論的研究前景和作者今后要努 力的研究方向 3 關(guān)于圖的上可嵌入性研究 基本概念和相關(guān)定理 2 1 基本概念 本文考慮的圖，若無(wú)指明均指有限無(wú)向的連通圖其他未加說(shuō)明的術(shù) 語(yǔ)和記號(hào)均同文獻(xiàn) 4 2 】【4 3 】個(gè)圖g 是指一個(gè)有序三元組( y ( g ) ，e ( g ) ，惦) ， 其中v ( c ) 是非空的頂點(diǎn)集，e ( g ) 是不與v ( c ) 相交的邊集，而惦是 關(guān)聯(lián)函數(shù)，它使g 的每條邊對(duì)應(yīng)于g 的無(wú)序頂點(diǎn)對(duì)1 v i = n 稱為圖g 的階設(shè)伽e ，則稱頂點(diǎn)u ，t ，為相鄰頂點(diǎn)，否則，稱缸，u 為非鄰頂點(diǎn) 假設(shè)y 是y 的一個(gè)非空子集，以為頂點(diǎn)集，以兩端點(diǎn)均在中 的邊的全體為邊集所組成的子圖，稱為g 的由y 7 導(dǎo)出的子圖，記為a v 1 g 的兩個(gè)頂點(diǎn)t t ，u 稱為連通的，如果在g 中存在從亂到鈔的路連通是 頂點(diǎn)集v ( g ) 上的一個(gè)等價(jià)關(guān)系于是存在v ( g ) 的一個(gè)分類，把v ( v ) 分 成非空子集，k ，k ，使得兩個(gè)頂點(diǎn)u ，秒是連通的當(dāng)且僅當(dāng)它們屬于 同一個(gè)子集k 子圖g f 】，g 【】，g 【蟈稱為g 的連通分支若g 只有 一個(gè)分支，則稱g 是連通的；否則，稱g 是不連通的若v ( a ) 的子集 y 使得v ( a ) 一v 不連通，則y 7 稱為v ( g ) 的頂點(diǎn)割k 頂點(diǎn)割是指有k 個(gè)元素的頂點(diǎn)割若g 至少有一對(duì)相異的不相鄰頂點(diǎn)，則g 所具有的k 頂點(diǎn)割中最少的k ，稱為g 的連通度，記為k ( g ) 若k ( g ) k ，則稱g 為舡 連通的對(duì)v ( g ) 的子集s 和s 7 ，用【ss 7 】表示一個(gè)端點(diǎn)在s 中，另一個(gè) 端點(diǎn)在中的所有邊的集合所謂g 的邊割是指形為【s 剛的e ( g ) 的 子集，其中s 是v ( a ) 的非空真子集一個(gè)k 邊割是指有k 個(gè)元素的邊 割若g 是非平凡的，g 的所有k 邊割中最少的k ，稱為g 的邊連通度， 記為( g ) 若( g ) k ，則稱g 為舡邊連通的稱圖日為圖g 的子圖， 如果v ( h ) 冬y ( g ) ，e ( h ) 冬e ( g ) ，并且婦是惦上的限制g 的生成子圖 是指滿足v ( h ) = v ( c ) 的子圖日不含圈的圖稱為無(wú)圈圖，連通的無(wú)圈圖 稱為樹(shù)；g 的生成樹(shù)是指g 的生成子圖，它同時(shí)又是樹(shù)設(shè)d 是g 的一 5 碩士學(xué)位論文 個(gè)點(diǎn)子集，即d y ( g ) ，若g 中每一點(diǎn)或者在d 中，或者與d 中某一點(diǎn) 鄰接，則稱d 是g 的一個(gè)支配集，g 中點(diǎn)數(shù)最少的支配集稱為最小支配 集；最小支配集中點(diǎn)的數(shù)目稱為支配數(shù)，記為r n ( a ) 曲面指一個(gè)連通緊致2 - 維閉流形曲面分為定向曲面與不可定向曲 面一個(gè)可定向曲面s 是由一個(gè)球面添上h 個(gè)環(huán)柄得到不可定向曲面 是由一個(gè)球面挖掉k 個(gè)圓盤(pán)而分別補(bǔ)上m s b i u s 帶得到其中，島稱為 球面，毋稱為環(huán)面，島稱為雙環(huán)面；l 稱為射影平面，2 稱為克萊 因瓶 一個(gè)圖g 在曲面s 上的一個(gè)開(kāi)二胞腔嵌入是指g 能畫(huà)在s 上使得 邊與邊之間除頂點(diǎn)外不再相交，且在s 上去掉g 的頂點(diǎn)與邊之后的每個(gè) 連通分支與開(kāi)圓盤(pán)同胚此時(shí)，每個(gè)開(kāi)圓盤(pán)稱為圖g 在s 上的一個(gè)面 注意到，不連通的圖在任意曲面上不存在2 胞腔嵌入圖g 的最大定向 虧格( 簡(jiǎn)稱為最大虧格) ，用伽( g ) 表示，是指最大的整數(shù)k 使得g 能2 - 胞 腔嵌入虧格為k 的定向曲面s 上圖的定向虧格，用，y ( g ) 表示，( 或不可 定向虧格用彳( g ) 表示) 是指最小的整數(shù)k 使得g 在虧格為k 的定向( 或 不可定向) 曲面s 上有2 胞腔嵌入設(shè)g 是一個(gè)具有個(gè)點(diǎn)，( 條邊的 圖，若g 在一個(gè)虧格為g 的( 定向或不定向) 曲面有2 胞腔嵌入，且具有 7 - 個(gè)面，則由e u l e r 公式一e + r = 2 2 9 ( s 定向) 或一e + 7 = 2 一g ( s 不 定向) ，因?yàn)槿魏我粋€(gè)圖在任意曲面上的2 - 胞腔嵌入中至少有一個(gè)面，由 最大虧格的定義及e u l e r 公式，即有伽( g ) 【竽j ，其中z ( a ) = e t ，+ 1 稱為圖g 的b e t t i 數(shù)，即圈秩數(shù)( 對(duì)任意實(shí)數(shù)z ，h 表示不超過(guò)z 的最大 整數(shù)) 同時(shí)，若7 m ( g ) = 【華j 稱圖g 是上可嵌人的 對(duì)于任意集合x(chóng) ，用l x l 表示x 的基數(shù)；設(shè)y 為圖g 的任意邊子集， g y 表示從g 中去掉y 中的所有邊所得到的圖；設(shè)g 為連通圖，且t 為g 的一棵生成樹(shù)，記f ( g ，t ) 表示g e ( t ) 中邊數(shù)為奇數(shù)的連通分支個(gè) 數(shù)，我們稱( g ) = 噸n ( g ，t ) 為g 的b e t t i 虧數(shù)，這里m i n 取遍g 的所有生 成樹(shù)t 由定義，對(duì)g 的任意生成樹(shù)丁，均有( g ，t ) 三f ( g ) - - z ( a ) ( m o d2 ) 6 關(guān)于圖的上可嵌入性研究 設(shè)a e ( g ) 為圖g 的邊子集，記號(hào)c ( g a ) 及b ( v a ) 分別表示g a 所有連通分支數(shù)及g a 的具有b e t t i 數(shù)為奇數(shù)的所有連通分支數(shù)設(shè) r ，b ，最( 七2 ) 為圖g 的k 個(gè)不相交的連通子圖，記號(hào)e ( r ，易，r ) 表示g 中2 個(gè)端點(diǎn)分別在2 個(gè)不同的只和f j 0 歹，1 i ，歹k ) 中的邊 集；另外，對(duì)g 的任意子圖f ，記號(hào)e ( eg ) 表示g 中一個(gè)端點(diǎn)屬于尸，而 另一個(gè)端點(diǎn)不屬于f 的邊集 本文將一個(gè)2 部圖記為g = x ，y ；e ) ，其中v ( g ) = xuve ( g ) = e = z ! i z x ，y y 對(duì)任意的a e ( g ) ，只為g a 的一個(gè)連通 分支，記r = ( x ，m ；毋) ，i = 1 ，2 ，k 其中y ( 尻) = 五uy , ，e ( x ，g ) = e = x y l x 咒，y 譬y ( r ) ) ，e ( m ，g ) = e = x y y k ，z 譬y ( 冠) ，且 e ( e ，g ) = e ( 五，g ) u e ( k ，g ) 將圖稱為多重完全圖，若它有一個(gè)基礎(chǔ)圖為完全圖；將圖稱為多重 完全2 部圖，若它有一個(gè)基礎(chǔ)圖為完全2 - 部圖圖g 的頂點(diǎn)d 劃分 是指：g 的一個(gè)頂點(diǎn)劃分 ，k ，使得每個(gè)g m 為多重完全圖 ( 1 i 七) ；圖g 的頂點(diǎn)b 劃分是指：g 的一個(gè)頂點(diǎn)劃分 ，k ) ， 使得每個(gè)g 瞰】為多重完全2 部圖( 1 i 七) ；圖g 的頂點(diǎn)a 劃分是指： g 的一個(gè)頂點(diǎn)劃分 ，圪) ，使得每個(gè)g 【吲為多重完全圖或多重完 全二部圖( 1 i 七) 7 碩士學(xué)位論文 2 2 相關(guān)定理與事實(shí) 圖的上可嵌入性，是由一個(gè)圖的最大虧格決定的前些年，文獻(xiàn)【3 】 給出了最大虧格的計(jì)算公式和判斷圖是上可嵌入的充要條件 定理i 【3 】設(shè)g 為圖，則 1 ) 伽( g ) = 華； 2 ) g 是上可嵌入的當(dāng)且僅當(dāng)( g ) 1 由定理i 知圖的上可嵌入性和最大虧格由b e t t i 虧數(shù)( g ) 確定對(duì) 一個(gè)圖g 的最大虧格的研究可轉(zhuǎn)化為對(duì)參數(shù)( g ) 的研究，關(guān)于( g ) 文 獻(xiàn)【4 】給出了如下組合表達(dá)式： 定理l i 【4 】若g 是一個(gè)圖，則f ( g ) 2 m c e s ( x g ) c ( g a ) + 6 ( g a ) 一i a i 一1 ) 許多關(guān)于上可嵌入性研究的文獻(xiàn)都用到了以下定理，也就是文獻(xiàn)【5 j 給出的非上可嵌入圖所具有的結(jié)構(gòu)特征： 定理【5 】設(shè)g 為圖，若g 不是上可嵌入的，即( g ) 2 ，則存在g 的邊子集a 滿足下列性質(zhì)： ( 1 ) c ( g a ) = b ( a a ) 2 ，且對(duì)g a 的任意連通分支f ，都有 f l ( f ) = 1 ( r o o d2 ) ； ( 2 ) 對(duì)于g a 的任意連通分支f ，f 是g 的點(diǎn)導(dǎo)出子圖； ( 3 ) 對(duì)于g a 的任意七忙2 ) 個(gè)不同連通分支只，b ，r ，有 i e ( 日，f 2 ，最) i 2 k 一3 ，特別的，當(dāng)k = 2 時(shí)，i e ( f 1 ，兄) l l ； ( 4 ) ( g ) = 2 c ( g a ) 一i a i 一1 在定理的條件和結(jié)論下，很容易得到以下事實(shí)： 事實(shí)1 對(duì)g a 的任意連通分支f ，若g 是缸邊連通的( k 1 ) ，則 i e ( eg ) i 七； 8 關(guān)于圖的上可嵌入性研究 事實(shí)2 當(dāng)g 是無(wú)環(huán)連通圖時(shí)， i y ( 只) i 2 ，當(dāng)g 是簡(jiǎn)單連通圖時(shí)， i v ( f o i 3 ；特別的，當(dāng)g 是簡(jiǎn)單連通2 - 部圖時(shí)，i v ( f o i 4 ，且i x i 2 ，l k i 2 ； 土 事實(shí)3 當(dāng)g 是簡(jiǎn)單連通圖時(shí)，2 a l = el e ( f i ，g ) i ；特別的，當(dāng)g 是 = 1 七蠡 簡(jiǎn)單連通二部圖時(shí)， i a i = i e ( 五，g ) i = i e ( m ，g ) i ； i = li = l 事實(shí)4 必存在某個(gè)f c ( c a ) 使得1 l e ( f g ) i 3 9 關(guān)于圖的上可嵌入性研究 3 圖的上可嵌人性與圈中頂點(diǎn)度 結(jié)合圖的一些參數(shù)來(lái)研究圖的上可嵌入性，近年來(lái)成為許多圖論學(xué) 者的研究方向目前，已有很多文獻(xiàn)研究了最大虧格與圖的點(diǎn)或邊連通 性、直徑、半徑、圍長(zhǎng)、頂點(diǎn)度、最小度、2 - 因子等之間的關(guān)系關(guān)于 頂點(diǎn)度與圖的上可嵌入性或最大虧格的關(guān)系研究，已經(jīng)有部分學(xué)者做了 一些工作例如文獻(xiàn)【2 2 】從非鄰節(jié)點(diǎn)度和出發(fā)研究了圖的上可嵌入性； 文獻(xiàn) 2 5 】得到了二部圖的上可嵌入性與相關(guān)頂點(diǎn)度和的關(guān)系；而文獻(xiàn)【2 6 】 得到了范條件圖是上可嵌入的本章則用圖的圈中頂點(diǎn)最大度來(lái)研究圖 的上可嵌入性，得到了一些新的結(jié)果 3 1 一般的2 - 邊連通簡(jiǎn)單圖 首先，我們討論一般的二邊連通簡(jiǎn)單圖，根據(jù)第二章中定理關(guān)于 非上可嵌入圖的充要條件，我們得到以下定理： 定理3 1 設(shè)g 是二邊連通簡(jiǎn)單圖，若對(duì)g 中任意圈c ，存在點(diǎn)z c 滿足： d ( z ) 下i v ( c ) l + 1 ， 則圖g 是上可嵌入的，且不等式的下界是不可達(dá)的 證明反證法假設(shè)g 是不能上可嵌入的，則存在邊集a e ( g ) 滿 足定理中所有性質(zhì)令只，b ，最( 七= b ( g a ) ) 是g a 的所有連通 分支因?yàn)間 是二邊連通圖，所以i e ( r ，g ) i 2 , i = 1 ，2 ，k 由定理 ( 3 ) 知k 3 由事實(shí)2 知i y ( r ) i 3 ( 1 i 七) ，又因p ( 只) 為奇數(shù)，且g 為簡(jiǎn)單 圖，易知足中必含一個(gè)圈，記為c ；i 由條件知必存在一點(diǎn)戤g 滿足 d ( x i ) 峰掣+ 1 因?yàn)檎缡欠种 內(nèi)的一個(gè)點(diǎn)，所以分支e 內(nèi)最多有 1 1 碩士學(xué)位論文 i y ( 只) i 1 個(gè)其它頂點(diǎn)與毛相鄰；而e ( 只，g ) 表示g 中一個(gè)端點(diǎn)屬于e ， 另一個(gè)端點(diǎn)屬于其他分支的邊集，又由定理( 3 ) 知任意兩個(gè)分支最多有 一條邊相連，則頂點(diǎn)甄最多與l e ( f i ，g ) 1 個(gè)分支有邊相連故 對(duì)所有分支求和得 即 d ( x i ) i y ( e ) i 一1 + i e ( f i ，g ) i k知k d ( x t ) ( i y ( e ) i - 1 ) + i e ( 只，a ) l ， i - - - - ii = lt = 1 k七k e d ( x i ) l y ( e ) i k + l e ( f i ，g ) i ， i = li = 1i = l k七 其中l(wèi) y ( r ) i = i v ( a ) 1 由事實(shí)3 知i e ( 只，g ) i = 2 川，并且i a i = i - - - - ii = l i e ( f 1 ，b ，f k ) i 2 k 一3 ，故有 七 d ( x i ) i v ( c ) l k + 2 ( 2 k 一3 ) ( 1 ) i = 1 由條件又有d ) 甲+ 1 ，則 毒堆抄( 掣娜 ( 2 ) l = l 由不等式( 1 ) 和( 2 ) 得： ( i v ( a ) 1 + 1 ) 七 l y ( g ) l k + 2 ( 2 七一3 ) ( 蠡3 ) ， 由上式變形可得 ( k 一3 ) i v ( a ) l 6 k 一1 8 ( k 3 ) 當(dāng)k = 3 時(shí)，由上式得到一個(gè)矛盾不等式0 o ； 當(dāng)k 4 時(shí)，由上式解得i y ( g ) i ”不能用冀打代替我們可以通過(guò)構(gòu)造 下面的圖類來(lái)說(shuō)明這一點(diǎn) g i 圖3 1 ( a ) y g 2 圖3 1 ( b ) 圖3 1 圖3 2 g 3 圖3 1 ( c ) 在圖3 1 中，g l ，g 2 ，g 3 是三個(gè)同構(gòu)的圖，它們均由2 m + l ( m = 0 ，1 ，2 ，) 個(gè)三 圈構(gòu)成每個(gè)圖的所有三圈都有一個(gè)公共頂點(diǎn)，我們將其稱為。支點(diǎn)力 1 3 碩士學(xué)位論文 如圖3 1 所示，三個(gè)圖的支點(diǎn)分別記作z ，y 現(xiàn)在，我們依次連接三個(gè) 支點(diǎn)，得到一個(gè)圖g 4 ( 見(jiàn)圖3 2 ) 在g 4 中，l y ( g 4 ) i = 3 ( 2 ( 2 m4 - 1 ) 4 - 1 ) = 1 2 m4 - 9 , d ( x ) = d ( y ) = d ( z ) = 2 ( 2 m4 - 1 ) 4 - 2 = 4 m4 - 4 = v l k l 3 q d l4 - 1 ，容易看出圖 g 4 的每一個(gè)圈中都至少存在一個(gè)度為。v l 業(yè)q 。_ d i4 - 1 井的頂點(diǎn)下面再說(shuō)明 g 4 不是上可嵌入的取g 4 中邊集a ，= z ! ，y z ，z z ) ，g 4 a l 有三個(gè)分支， 且不難觀察到每個(gè)分支的b e t t i 數(shù)為奇數(shù)，即c ( g 4 a 。) = b ( g 4 a 。) = 3 由定理知 f ( g 4 ) c ( g 4 a 1 ) + 6 ( g 4 a 1 ) 一1 月l i 一1 = 2 從而g 4 不是上可嵌入的所以從圖g 4 可得不等式中。 ”不能用q ” 來(lái)代替，也就是說(shuō)定理中的界。甲4 - 1 丹是不可達(dá)的另外，由于m 可 以取0 或任意正整數(shù)，我們可以得到無(wú)窮多個(gè)這樣的圖例口 由定理3 1 很容易得到以下推論： 推論3 1 設(shè)g 是2 邊連通簡(jiǎn)單圖，若g 的最小度6 ( g ) 甲4 - 1 ， 則g 是上可嵌入的 3 22 - 邊連通簡(jiǎn)單2 部圖 在定理3 1 中我們討論了一般的2 邊連通簡(jiǎn)單圖，本節(jié)我們討論一 種特殊情況，也就是當(dāng)這個(gè)圖是簡(jiǎn)單二部圖時(shí)，得到下面的一個(gè)定理和 簡(jiǎn)單的推論 定理3 2 設(shè)g = 【ky ；e ) 為簡(jiǎn)單2 部圖，且是2 - 邊連通的i x l = m ，i y i = n ( m ，n 3 ) ，若對(duì)g 中任意圈c ，存在點(diǎn)z c 且z x 滿足： d ( z ) 詈“ 則圖g 是上可嵌入的，且不等式的下界是不可達(dá)的 1 4 關(guān)于圖的上可嵌入性研究 證明反證法假設(shè)g 是不能上可嵌入的，則存在邊集a e ( g ) 滿 足定理中所有性質(zhì)令日，而，r ( 七= b ( c a ) ) 是g a 的所有連通 分支因?yàn)間 是一個(gè)二部圖，所以g a 的每一個(gè)連通分支只也是一個(gè) 參部圖記只= ( x ，k ；日) ，i = 1 ，2 ，七y ( r ) = 五u m 由定n i i i ( 3 ) 知 k 3 由事實(shí)2 知1 x i l 2 ，i k i 2 ，又因p ( r ) 為奇數(shù)，且g 為簡(jiǎn)單圖，易知 r 中必含一個(gè)圈，記為g 由條件知必存在一點(diǎn)g 滿足d 慨) 詈+ 1 因?yàn)橹檬欠种 內(nèi)點(diǎn)集五中的一個(gè)點(diǎn)，所以分支e 內(nèi)最多有l(wèi) 1 個(gè)y 型頂點(diǎn)與戤相鄰，而e ( x i ，g ) 表示g 中一個(gè)端點(diǎn)屬于x ，另一個(gè)端點(diǎn)屬 于其他分支的邊集則頂點(diǎn)毛最多與l e ( x i ，g ) 1 個(gè)分支有邊相連故 d ( x i ) si k i + i e ( x ，g ) i ， 對(duì)所有分支求和得 知 kk d ( 而) i y , i + i e ( x t ，c ) j ， i = 1i - - - - li = 1 其中el k i = i y i = 禮由事實(shí)3 知i e ( 置，g ) j = l a i ，且l a i = i e ( r ，f 2 ，r ) i 2 k 一3 ，故有 d ( 黽) n + ( 2 k 一3 ) ； ( 3 ) = l 由條件又有d ( 黽) 署+ 1 ，則 七 d ( z i ) ( ；+ 1 ) 七 ( 4 ) 由不等式( 3 ) 和( 4 ) 得： ( 三+ 1 ) 七 n + ( 2 七一3 ) ( 七3 ) ， 由上式變形可得 ( k 一3 ) - 3 k 一9 ( k 3 ) 1 5 碩士學(xué)位論文 當(dāng)k = 3 時(shí)，由上式得到一個(gè)矛盾不等式0 o ； 當(dāng)k 4 時(shí)，由上式解得n 一不能用“一代替和定理3 1 的證明類似，我 們可以通過(guò)構(gòu)造下面的圖類來(lái)說(shuō)明這一點(diǎn) a g 5 剪1 圖3 3 ( a ) z 2 1 y 2 t j 6 圖3 3 ( b ) 黝 蜘 ( i 7 圖3 3 ( c ) 圖3 3 1 6 關(guān)于圖的上可嵌入性研究 在圖3 3 中，g 5 ，g 6 ，g 7 是三個(gè)同構(gòu)的2 部圖，它們均由2 m + l ( m = 0 ，1 ，2 ， ) 個(gè)四圈構(gòu)成每個(gè)圖的所有四圈都有一條公共邊，我們將其稱為“支 邊斗如圖3 3 所示，上面三個(gè)圖的支邊分別記作x l y 。，x 2 y 2 ，x 3 蜘現(xiàn)在，我 們依次連接_ y a x 2 骨、。y 2 x a 力、_ y s x l ”，得到下面的一個(gè)圖g 8 g s 圖3 4 在圖3 4 所示g 8 中，n = i y i = 3 ( 2 m + 2 ) = 6 m + 6 , d ( x i ) = d ( x 2 ) = d ( z 。) = 2 m + 3 = 詈+ 1 ，容易看出圖g 8 的每一個(gè)圈中都至少存在一個(gè)度為 。詈+ 1 骨的x 型頂點(diǎn)下面再說(shuō)明g s 不是上可嵌入的取g s 中邊集 a 2 = z l y s ，z 3 y 2 ，z 2 y 。) ，g 8 a ：有三個(gè)分支，且不難觀察到每個(gè)分支的b e t t i 數(shù)為奇數(shù)，即c ( g s a 2 ) = b ( g s a z ) = 3 由定理i i 知 ( g s ) c ( g s a 2 ) + b ( g s 2 ) 一i a 2 i 一1 = 2 從而g 8 不是上可嵌入的所以從圖g 8 可得不等式中。 一不能用誓丹 來(lái)代替，也就是說(shuō)定理中的界。詈+ 1 骨是不可達(dá)的另外，由于m 可以 取0 或任意正整數(shù)，我們可以得到無(wú)窮多個(gè)這樣的圖例 口 1 7 碩士學(xué)位論文 根據(jù)2 - 部圖的性質(zhì)，頂點(diǎn)集x 與y 在圖中的地位和作用是對(duì)稱的， 所以定理3 2 也可以寫(xiě)為下面的形式： 定理3 2 設(shè)g = x ，y ；e ) 為簡(jiǎn)單2 一部圖，且是2 邊連通的i x i = m ，i y l = n ( m ，t t 3 ) ，若下列條件有任意一個(gè)滿足： ( 1 ) 對(duì)g 中任意圈c ，存在點(diǎn)z c 且z x 滿足： d ( z ) 曇+ l ； ( 2 ) 對(duì)g 中任意圈c ，存在點(diǎn)y c 且9 y 滿足： d ( y ) i t t4 - 1 ； 則圖g 是上可嵌入的，且不等式的下界是不可達(dá)的 由定理3 2 很容易得到以下推論： 推論3 2 設(shè)g = x ，y ；e ) 為簡(jiǎn)單2 - 部圖，且是2 - 邊連通的i x i = m ，i y i = n ( m ，n 3 ) ，y ( g ) = xuy 若g 的最小度占( g ) 皿3 劍，則g 是上 可嵌入的 1 8 關(guān)于圖的上可嵌入性研究 與支配集有關(guān)的上可嵌人圖 在圖的上可嵌入性與圖的各項(xiàng)參數(shù)之間關(guān)系的研究中，支配集與支 配數(shù)是一個(gè)重要的方面圖g 的一個(gè)支配集d 是指g 的一個(gè)點(diǎn)子集， 使得g 中每一點(diǎn)或者在d 中，或者與d 中某一點(diǎn)鄰接g 中點(diǎn)數(shù)最 少的支配集稱為最小支配集，最小支配集中點(diǎn)的數(shù)目稱為支配數(shù)文獻(xiàn) 【3 9 】利用圖g 的支配數(shù)和圍長(zhǎng)給出了g 的b e t t i 虧數(shù)( g ) 的一個(gè)上界， 從而給出了最大虧格似( g ) 的一個(gè)下界本章則在此基礎(chǔ)上考慮圖g 的 支配集及一些相關(guān)條件，確定了兩類上可嵌入圖，豐富了這方面的結(jié)果 4 1 以輪為支配集的上可嵌人圖 定義4 1 稱圖w 為一個(gè)輪，如果v ( w ) = z ，y l ，y 2 ，軌) ，e ( w ) = z 璣忙= 1 ，2 ，) u y t 犰+ 1 l i = 1 ，2 ，t ，t + l ( m o d ) 】，且點(diǎn)z 稱為該輪w 的中心 在給出了輪的定義后，我們得到一類以輪為支配集的上可嵌入圖 定理4 1 設(shè)g 是無(wú)環(huán)連通圖，如果g 中含有一個(gè)子圖為輪，且 v ( w ) = z ，y ，拋，y t ( t23 ) 為圖g 的一個(gè)支配集，則圖g 是上可嵌入 的 證明反證法假設(shè)g 是不能上可嵌入的，則存在邊集a e ( c ) 滿 足定理中所有性質(zhì)令r ，尼，r ( 鳧= c ( c a ) ) 是g a 的所有連通 分支，則k 2 我們先得到以下斷言： 斷言1 不存在連通分支只，使得v ( w ) y ( r ) 即支配集v ( w ) 中的 所有頂點(diǎn)不可能同時(shí)含于同一個(gè)連通分支中 證明若存在連通分支只，使得v ( w ) y ( 只) ，因?yàn)閗 2 ，所以存在 連通分支乃o i ) ，而由事實(shí)2 知i v ( f j ) l 2 根據(jù)支配集的定義，馬中 1 9 碩士學(xué)位論文 所有頂點(diǎn)均與v ( w ) 中頂點(diǎn)相鄰于是l e ( f i ，b ) l 2 ，與定理( 3 ) 矛盾 故斷言成立 斷言2 對(duì)于任意一個(gè)連通分支最，有i v ( w ) n y ( 只) i 1 證明反證假設(shè)存在連通分支只，使得i v ( w ) ny ( 只) i 2 根據(jù)定 義4 1 ，設(shè)點(diǎn)z 為輪的中心分以下兩種情況討論： 情形jz y ( 只) 不妨設(shè) z ，們) cy ( 只) 且y l + 1 y ( 毋) o i ) ，則因?yàn)?點(diǎn)z ，y t ，y t + 。都是輪中的點(diǎn)，z 又是輪的中心，故點(diǎn)z ，y l 均與點(diǎn)y l + l 相鄰，于是i e ( 只，毋) l 2 ，與定理( 3 ) 矛盾 情形2z 譬v ( r ) 不妨設(shè) 饑，) cy ( r ) 且z y ( 乃) o i ) ，同理有 x y l ，z ) ce ( ) ，此時(shí)i e ( r ，乃) i 2 ，與定理( 3 ) 矛盾 由以上兩種情況可知，斷言2 成立 由斷言2 可知，在g a 的k 個(gè)連通分支中，有t + 1 個(gè)分支分別含有 支配集v ( w ) 中的一個(gè)頂點(diǎn)不妨設(shè)該t + 1 個(gè)分支為r ，b ，r + l ，容 易得到e ( w ) e ( r ，局，只+ 1 ) 而l e ( w ) i = 2 t ，則i e ( r ，r ，r + 1 ) l i e ( ) i = 2 t 2 ( t + 1 ) 一3 此結(jié)果又與定理( 3 ) 矛盾故定理成立 口 4 2 以完全2 - 部圖為支配集的上可嵌人圖 本節(jié)討論以完全2 部圖為支配集的情況，為方便定理的證明，首先 給出一個(gè)引理 引理4 1 設(shè)，( z ，y ) = x y 一2 x 一2 y4 - 4 ，當(dāng)z 3 ，y 4 時(shí)，有，( z ，y ) 1 ( 3 ，4 ) = 2 0 證明缸o(hù) f = y - 2 ，苗= x - 2 顯然當(dāng)z 3 ，y 4 時(shí)，鬈 o ，苗 0 所以 ，( z ，y ) 分別關(guān)于z ，y 是嚴(yán)格單調(diào)遞增函數(shù)，故有，( z ，y ) f ( 3 ，4 ) = 2 0 引理證畢 口 定理4 2 設(shè)g 是無(wú)環(huán)連通圖，如果g 中含有一個(gè)子圖為完全2 - 部圖 2 0 關(guān)于圖的上可嵌入性研究 d = ( x ，y ；e ) ，且v ( d ) = xuy 為圖g 的一個(gè)支配集( 其中l(wèi) x i 3 ，i y i 4 ) ， 則圖g 是上可嵌入的 證明反證法設(shè)g 不是上可嵌入的，則存在邊集a e ( c ) 滿足定 理所有性質(zhì)令r ，尼，r ( 七= c ( g a ) ) 是g 以的所有連通分支， 則k 2 不妨設(shè)x = z 1 ，z 2 ，z m ，y = 籮1 ，v 2 ，) ，于是m 3 ，n 4 我們先得到以下斷言： 斷言1 不存在連通分支r ，使得v ( d ) y ( 只) 即支配集v ( d ) 中的 所有頂點(diǎn)不可能同時(shí)含于同一個(gè)連通分支中 證明證明過(guò)程完全同定理4 1 中斷言1 類似 斷言2 不存在連通分支只，使得x y ( 只) 或y y ( 只) 證明若x y ( 只) ，即 z 。，勛，) y ( 只) 則由斷言1 知必存在 y l y ( 弓) 0 i ) 因?yàn)閐 = ( x ，y ；e ) 為完全二部圖，則y z 與z l ，z 2 ，z 仇 都有邊相連，此時(shí)有l(wèi) e ( r ，毋) i 仇3 ，與定理性質(zhì)( 3 ) 矛盾同理，不 存在連通分支只，使得y y ( e ) 故斷言成立 斷言3 對(duì)于任意連通分支只，有i xny ( 只) i 1 且i y ny ( 只) i 1 證明反證假設(shè)存在連通分支尻，使得l x ny ( e ) i 2 不妨設(shè) z l ，勛】y ( 只) 由斷言2 知必有一點(diǎn)肌y ( 乃) o i )