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/).

Download article (PDF)

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  -