关于图的控制数与全控制数的研究

摘要

图的控制理论是图论的一个重要分支.自1998年以来，图的控制理论发展迅速.在发展的过程中，提出了许多与控制数相关的概念，并得到广泛的研究.给定图G=(V(G),E(G)).V(G)的一个子集S称为图G的控制集，如果V(G)- S的任意点均至少与S中一点相邻.γ(G)表示图G的最小控制集的基数，称为图G的控制数. S称为图G的全控制集，如果V(G)中任意一点均至少与S中一点相邻.γt(G)表示图G的最小全控制集的基数，称为图G的全控制数.
　　本文主要对倍图的控制数与直径为3的4-全控制点临界图进行研究.首先通过研究倍图的控制集，得到了倍图的控制数与全控制数相等的结论，并刻画其倍图的控制数为2,3,4的图.其次通过研究直径为3,最小度至少为2的4-全控制点临界图，证明了除6-圈外最小度至少为2的4-全控制点临界图的阶至少为8,刻画所有阶为8直径为3的这类图，并且证明存在2n+2(n大于等于2)阶的直径为3的4-全控制点临界n正则图.

目录

封面

目录

中文摘要

英文摘要

第1章 绪 论

1 .1 研究背景及现状

1.2 本文的主要内容和安排

第2章预备知识

2.1 符号和基本概念

2 .2 特殊图的控制数、倍图及全控制点临界图的相关

第3章倍图的控制数

3 .1 倍图控制数为2的图

3 .2 倍图控制数为3的图

3 .3 倍图控制数为4的图

第4章 直 径 为3 的4-全控制点临界图的存在性

4 .1 含有悬挂点的直径为3的4-全控制点临界图

4 .2 无悬挂点的直径为3的4-全控制点临界图

结论

参考文献

硕士期间发表或录用的学术论文

声明

致谢