单圈图的全控制数与零化数

发布时间：2018-03-06 19:24

  本文选题：全控制数　切入点：零化数　出处：《新疆大学》2015年硕士论文　论文类型：学位论文

【摘要】：上世纪六十年代以来,图论作为年轻的数学分支,获得了空前的发展,在物理学,化学,生物学,网络理论,信息科学以及计算机科学等学科中有着极其广泛的应用.图论作为组合数学的一个分支,受到了各方面的普遍重视.对于任意一个非平凡图,其全控制数与零化数这两个参数之间是有关系的.这两个参数在很多领域有着广泛的应用,如利用图的零化数计算其独立数的上界等.本文主要研究单圈图的这两个参数之间的关系.给定一个简单图G,γt(G)和a(G)分别表示图G的全控制数和零化数.Desormeaux,Haynes和Henning(离散应用数学.161(2013)349-354)提出了一个猜想:如果图G是一个顶点数为n的连通非平凡图,是否有γt(G)≤a(G)+1成立?他们证明了对于任意一个非平凡树T,此猜想是成立的.在本文中,我们证明了对于一个顶点数为n的连通单圈图G,则γt(G)≤a(G)+1,等号成立当且仅当G～=Cn且n不被4整除.
[Abstract]:Since -40s, as a young branch of mathematics, graph theory has gained unprecedented development in physics, chemistry, biology, network theory, As a branch of combinatorial mathematics, graph theory is widely used in the fields of information science and computer science. There is a relationship between the total domination number and the zero number. These two parameters are widely used in many fields. For example, the upper bound of the independent number of a graph is calculated by using the zeroing number of a graph. In this paper, the relationship between these two parameters of a unicyclic graph is studied. Given a simple graph G, 纬 t0 G) and a G), respectively, the total domination number and zero number of graph G are denoted by the total domination number and zero number. Desormeaux.Haynes and Henning. In this paper, we present a conjecture: if G is a connected nontrivial graph with n vertices, Is there a 纬 TX G) 鈮，

本文编号：1576154