图的邻域全控制数研究

发布时间：2017-12-27 23:08

  本文关键词：图的邻域全控制数研究　出处：《华东师范大学》2016年博士论文　论文类型：学位论文

  更多相关文章： 控制集问题 邻域全控制集问题 动态规划 标号方法 树 Mycielski’s图

【摘要】：设G=(V,E)为一个简单图.图G的一个控制集D是V的一个子集使得V\D中的每个顶点都和至少一个D中的顶点相邻.G的控制数γ(G)是G的控制集的最小基数.图G的一个全控制集D是V的一个子集使得V中的每个顶点都至少和一个D中的顶点相邻.G的全控制数γt(G)是G的全控制集的最小基数.图G的一个邻域全控制集D(?)V是G的一个控制集且满足：对每个顶点u ∈V\D,u至少有一个邻点在N(D)中.G的邻域全控制数γnt(G)是G的邻域全控制集的最小基数.若G没有孤立点,则γ(G)≤γnt(G)≤γt(G)≤2γ(G)本文对与邻域全控制数相关的问题进行研究,主要做了以下几部分的工作：邻域全控制数问题是指对于给定的图G和数l,是否有γnt(G)≤l,即是否存在一个邻域全控制集S使得|S|≤l?在本文第二章证明了邻域全控制数问题对二部图和分裂图都是NP-完全的,然后用动态规划的方法给出了树的邻域全控制数的一个线性时间算法,并且把该算法推广到了点赋权树的赋权邻域全控制数情形上.在本文第三章,我们给出了所有满足γnt(T)=2γ(T)的树T的集族τ,并对这样的树的结构进行了刻画.图G的一个填装是指G的一个顶点集S使得S中任意两点在G中的距离都至少为3.一个图G的填装数ρ(G)是指G的填装的最大基数.用标号的方法构造出了所有满足γNT(G)=ρ(G)的图G的集族以及所有控制数等于邻域全控制数的森林集族.在本文第四章,我们考虑图的边数、阶数和邻域全控制数的关系,证明了若G是一个n阶m条边的连通图且G≠K2,则M≤?(n—γnt(G))(n一γnt.(G)+3).接着考虑了图的直径和其补图的邻域全控制数的关系,证明了若G没有孤立顶点且dim(G)≥3则γnt(G)=2.在本文第五章,我们用概率方法给出了一个n阶且最小度δ≥2的图G的邻域全控制数的上界.然后给出了一个最小度δ(G)≥2且围长9(G)≥5的连通图G的邻域全控制数的上界.在本文第六章,我们考虑图G的Mycielski's图μ(G)的邻域全控制数,证明了对一个没有孤立点的图G有γnt(μ(G))≤γnt(G)+1证明了对任意给定的正整数k1,存在一个没有孤立点的图G,使得差值γnt(G)一γnt(μ(G))等于k.接着考虑了μ(G)的邻域全控制数和G的控制数之间的关系,证明了对任意图G,γ(G)+1≤γnt(μ(G))≤γ(G)+2当γ(G)=1时：给出了γnt(μ(G))=γ(G)+1的充要条件,当γ(G)≥2时,给出了γnt(μ(G))=γ(G)+1的一个充分条件.
[Abstract]:璁綠=(V,E)涓轰竴涓�绠�鍗曞浘.鍥綠鐨勪竴涓�鎺у埗闆咲鏄疺鐨勪竴涓�瀛愰泦浣垮緱V\D涓�鐨勬瘡涓�椤剁偣閮藉拰鑷冲皯涓，

本文编号：1343564