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 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, . 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 等数据库收录! |
|