Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017)

Domination Numbers of Trees

Authors
Min-Jen Jou, Jenq-Jong Lin
Corresponding Author
Min-Jen Jou
Available Online May 2017.
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)

Volume Title
Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017)
Series
Advances in Intelligent Systems Research
Publication Date
May 2017
ISBN
978-94-6252-355-5
ISSN
1951-6851
DOI
10.2991/ammsa-17.2017.71How to use a DOI?
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  -