本文選題：完美2對集覆蓋圖 + n可擴圖　； 參考：《中山大學》2017年博士論文

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

本文編號：2048653