Domination Numbers of Trees
- DOI
- 10.2991/ammsa-17.2017.71How to use a DOI?
- Keywords
- domination number; tree; order; duplicated leaves
- Abstract
A set S of vertices is a dominating set of G if NG[S]=V(G). The domination number (G) of a graph G is the minimum cardinality among all dominating sets of G. The decision problem of determining the domination number for arbitrary graphs is NP-complete. Here we focus on trees. If x and x' are duplicated leaves adjacent to the same support vertex in a tree T, then (T - x')= (T). If T' can be obtained from T by adding some duplicated leaves, we can see that (T' )= (T ). So the maximum order of a tree T, which is (T)=k, is infinity. In this paper, we focus on trees which are without duplicated leaves. For k 1, we determine the minimum and maximum orders of the trees T which are without duplicated leaves and (T)=k. Moreover, we characterize the trees of minimum and maximum orders.
- Copyright
- © 2017, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Min-Jen Jou AU - Jenq-Jong Lin PY - 2017/05 DA - 2017/05 TI - Domination Numbers of Trees BT - Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017) PB - Atlantis Press SP - 319 EP - 321 SN - 1951-6851 UR - https://doi.org/10.2991/ammsa-17.2017.71 DO - 10.2991/ammsa-17.2017.71 ID - Jou2017/05 ER -