本文選題：完美2對(duì)集覆蓋圖 + n可擴(kuò)圖　； 參考：《中山大學(xué)》2017年博士論文

【摘要】：本文主要研究了完美2對(duì)集覆蓋圖和對(duì)集擴(kuò)展的若干性質(zhì)。設(shè)G表示一個(gè)圖,我們用V(G),E(G),ν,ε分別表示圖G的頂點(diǎn)集、邊集、頂點(diǎn)數(shù)、邊數(shù)。設(shè)v∈V(G),H是G的一個(gè)子圖。定義ΓH(v)={u|uv∈E(G)且u∈V(H)}。設(shè)D是G的子圖,定義ΓH(D)={u|uv∈E(G),v∈V(D),u∈V(H)}。如果H=G,則把ΓH(v)和ΓH(D)分別簡(jiǎn)寫(xiě)為Γ(v)和Γ(D)。圖G的完美2對(duì)集M是指G的生成子圖,滿足M中的每個(gè)分支或者是一條邊,或者是一個(gè)圈。如果圖G中的每條邊都屬于G的某個(gè)完美2對(duì)集,那么G就稱(chēng)為完美2對(duì)集覆蓋圖。圖G的偶雙蓋是這樣一個(gè)的偶圖,設(shè)其兩個(gè)分部為(U,W),圖G中每個(gè)頂點(diǎn)u都有兩個(gè)頂點(diǎn)u′、u′′,滿足u′∈U和u′′∈W。如果uv是G中一條邊,那么u′v′′和v′u′′也是G的偶雙蓋中的邊。在第2章中,對(duì)完美2對(duì)集覆蓋圖和偶雙蓋之間的關(guān)系進(jìn)行了研究,證明了滿足ν≥2的非偶圖G的偶雙蓋是1可擴(kuò)圖當(dāng)且僅當(dāng)G是完美2對(duì)集覆蓋圖。因此,我們?cè)O(shè)計(jì)了一個(gè)在O(√νε)時(shí)間內(nèi)判斷G是否是完美2對(duì)集覆蓋圖的多項(xiàng)式時(shí)間算法,該算法的時(shí)間復(fù)雜度是最優(yōu)的。更進(jìn)一步,證明了滿足ν≥2的非偶圖G的偶雙蓋是極小1可擴(kuò)圖當(dāng)且僅當(dāng)G是極小完美2對(duì)集覆蓋圖,并且對(duì)于G中任意邊e=xy,G中都有一個(gè)獨(dú)立集S,使得|ΓG(S)|=|S|+1,x∈S并且|ΓG-xy(S)|=|S|。設(shè)G是一個(gè)連通圖,n是一個(gè)正整數(shù)(n≤ν-22)。如果G中任何有n條邊的對(duì)集都可以擴(kuò)展成G中一個(gè)完美對(duì)集,那么就稱(chēng)G是n可擴(kuò)圖。婁定俊和于青林提出猜想:如果G是滿足ν≤6n的n可擴(kuò)圖,則G是哈密頓的。李粵平和婁定俊證明了對(duì)偶圖而言該猜想是成立的。在第3章中,對(duì)李粵平和婁定俊的該研究成果進(jìn)行了推廣,證明了如果G是滿足ν6n的n可擴(kuò)偶圖,則G有一個(gè)滿足|V(C)|≥6n的最長(zhǎng)圈C,并且|V(C)|的界是嚴(yán)格成立的。因此,如果G是n可擴(kuò)偶圖,則G中最長(zhǎng)圈的長(zhǎng)度至少是min{ν,6n}。我們對(duì)n可擴(kuò)偶圖中兩點(diǎn)間是否存在哈密頓路進(jìn)行了研究,在第4章中證明了:如果G=(X,Y)是滿足ν≤6n-2的n可擴(kuò)偶圖,則對(duì)于任意頂點(diǎn)對(duì)x∈X,y∈Y,G中都存在一個(gè)從x到y(tǒng)的哈密頓路,并且ν(G)的界是嚴(yán)格成立的。缺失d對(duì)集是指圖G中覆蓋除d個(gè)頂點(diǎn)之外所有頂點(diǎn)的一個(gè)對(duì)集。缺失0對(duì)集也叫作完美對(duì)集,缺失1對(duì)集也叫作近似完美對(duì)集。設(shè)G是一個(gè)連通圖,n是一個(gè)正整數(shù)(n≤ν-32)。如果G中任意大小為n的對(duì)集都能擴(kuò)展成一個(gè)近似完美對(duì)集,那么就稱(chēng)G是缺失n可擴(kuò)圖。Plummer證明了沒(méi)有平面圖是3可擴(kuò)的。在第5章中證明了連通度大于1的平面圖不是缺失6可擴(kuò)圖,并提出猜想:連通度大于1的平面圖不是缺失5可擴(kuò)圖。該成果為研究平面圖的缺失可擴(kuò)度找到了一個(gè)上界。連通度等于1的平面圖可以是缺失n可擴(kuò)的,其中n是任意正整數(shù)。
[Abstract]:In this paper, we study some properties of perfect 2-pair set covering graph and its extension. Let G denote a graph, and we use VG to denote the vertex set, edge set, vertex number and edge number of G respectively. Let v 鈭，

本文編號(hào)：2048653