首页 | 本学科首页   官方微博 | 高级检索  
     


Domination subdivision numbers of trees
Authors:H. Aram  O. Favaron
Affiliation:a Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, I.R., Iran
b L.R.I., UMR 8623, Université Paris-Sud, 91405 Orsay Cedex, France
Abstract:A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G)?S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number View the MathML source is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, View the MathML source. In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a linear algorithm for recognizing them.
Keywords:Trees   Domination number   Domination subdivision number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号