點滴的記錄

琐事，日常之事:

點滴的記錄:

大学生毕业论文设计：平面图的Dunbar猜想

•学号：PB06001074
•姓名：王晶
•年级：06级
•系别：数学系
•完成日期：2010年6月
•指导教师：徐俊明

摘要：
对一个非空图G（graph）， 如果G中的每一个顶点都在D 中或者与G的顶点相连，那么 D就被称为非空图的控制集 （dominating set），最小的 控制数（dominating number） 我们就用γ（G）表示。设E为 为G的一个边的集合，如果G- E的控制数大于G的控制数， 那么最小的集合E中边的数目 就称为束缚数b（G） （bondage number）。摘要Kang 和 Yuan 曾证明 过对任意联通的平面图 G来说 b(G)≤8。 Carlson 和 Develin 提 供过一个简单，原始的 证明：当G为平面图时 b(G)≤ min{8, △(G)+2}。 在本文中，我们将尝试 证明Dunbar的著名猜想 b(G) ≤ △+1；由于证明 本身困难，我们将先考 虑部分情况，就是连通 平面图，与此同时，我 们将只考虑△≤3的特殊 情况。

Abstract: 
Given a nonempty graph G, a set D of its vertices is a dominating set if every vertex of G is in D or adjacent to a vertex in D. The dominating number γ(G) of a graph G is defined t be the minumum size of a dominating set of G. If E is a edge set of G, the bondage number b(G) of a nonempty graph is defined to be the cardinality of the smallest set E of edges of G such that the graph G-E has domination number greater than that of G.Kang and Yuan proved b(G)≤8 for every connected planar graph G. Carlson and Develin presented a simple, intuitive proof that b(G)≤ min{8, △(G)+2}for all planar graphs G. In this paper, we conject that b(G) ≤ △+1 when 3≤△≤6. Since it is not very easy, we will consider △≤3 first especially for a connected planar graph.

关键词：束缚数（bondage number），控制数 （domination number），连通的平面图 （connected planar graph），度（degree），顶 点（vertex）

本 文 主 要 内 容第一章主要介绍的是本文的背景知识，以 及关于束缚数的研究历程和与之相关的部 分文献，以及现在的研究现状。第二章回顾了与束缚数有关的研究成果， 主要结论的列举，以及本文可能用的的 部分主要结论。第三章则为本文涉及的主要证明以及猜想和本文可能的 应用

http://www.slideshare.net/greentask/dunbars-conjecture-for-planar-graphs