完美2对集覆盖图和对集扩展的若干性质的研究

发布时间：2018-06-21 12:44

  本文选题：完美2对集覆盖图 + n可扩图　； 参考：《中山大学》2017年博士论文

【摘要】：本文主要研究了完美2对集覆盖图和对集扩展的若干性质。设G表示一个图,我们用V(G),E(G),ν,ε分别表示图G的顶点集、边集、顶点数、边数。设v∈V(G),H是G的一个子图。定义ΓH(v)={u|uv∈E(G)且u∈V(H)}。设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的偶双盖是这样一个的偶图,设其两个分部为(U,W),图G中每个顶点u都有两个顶点u′、u′′,满足u′∈U和u′′∈W。如果uv是G中一条边,那么u′v′′和v′u′′也是G的偶双盖中的边。在第2章中,对完美2对集覆盖图和偶双盖之间的关系进行了研究,证明了满足ν≥2的非偶图G的偶双盖是1可扩图当且仅当G是完美2对集覆盖图。因此,我们设计了一个在O(√νε)时间内判断G是否是完美2对集覆盖图的多项式时间算法,该算法的时间复杂度是最优的。更进一步,证明了满足ν≥2的非偶图G的偶双盖是极小1可扩图当且仅当G是极小完美2对集覆盖图,并且对于G中任意边e=xy,G中都有一个独立集S,使得|ΓG(S)|=|S|+1,x∈S并且|ΓG-xy(S)|=|S|。设G是一个连通图,n是一个正整数(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的哈密顿路,并且ν(G)的界是严格成立的。缺失d对集是指图G中覆盖除d个顶点之外所有顶点的一个对集。缺失0对集也叫作完美对集,缺失1对集也叫作近似完美对集。设G是一个连通图,n是一个正整数(n≤ν-32)。如果G中任意大小为n的对集都能扩展成一个近似完美对集,那么就称G是缺失n可扩图。Plummer证明了没有平面图是3可扩的。在第5章中证明了连通度大于1的平面图不是缺失6可扩图,并提出猜想:连通度大于1的平面图不是缺失5可扩图。该成果为研究平面图的缺失可扩度找到了一个上界。连通度等于1的平面图可以是缺失n可扩的,其中n是任意正整数。
[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