Dehgardai, N., Norouzian, S., Sheikholeslami, S. (2013). Bounding the domination number of a tree in terms of its annihilation number. Transactions on Combinatorics, 2(1), 9-16. doi: 10.22108/toc.2013.2652

Nasrin Dehgardai; Sepideh Norouzian; Seyed Mahmoud Sheikholeslami. "Bounding the domination number of a tree in terms of its annihilation number". Transactions on Combinatorics, 2, 1, 2013, 9-16. doi: 10.22108/toc.2013.2652

Dehgardai, N., Norouzian, S., Sheikholeslami, S. (2013). 'Bounding the domination number of a tree in terms of its annihilation number', Transactions on Combinatorics, 2(1), pp. 9-16. doi: 10.22108/toc.2013.2652

Dehgardai, N., Norouzian, S., Sheikholeslami, S. Bounding the domination number of a tree in terms of its annihilation number. Transactions on Combinatorics, 2013; 2(1): 9-16. doi: 10.22108/toc.2013.2652

Bounding the domination number of a tree in terms of its annihilation number

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $V-S$ is adjacent to some vertex in $S$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set in $G$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of edges in $G$. In this paper, we show that for any tree $T$ of order $n\ge 2$, $\gamma(T)\le \frac{3a(T)+2}{4}$, and we characterize the trees achieving this bound.

H. Aram, A. Bahremandpour, A. Khodkar, S. M. Sheikholeslami and
L. Volkmann Relating the annihilation number and the Roman
domination number of a tree. submitted.

2

Y. Caro and R. Pepper (2012). Degree Sequence Index Strategy. arXiv:1210.1805v1.

3

E. J. Cockayne, C. W. Ko and F. B. Shepherd (1985). Inequalities concerning dominating sets in
graphs. Technical Report DM-370-IR, Dept. Math. Univ. Victoria.

4

E. DeLaVina, C. E. Larson, R. Pepper and B. Waller (2010). Graffiti.pc on the 2-domination number of a graph. Congr. Numer.. 203, 15-32

5

E. DeLaVina, R. Pepper and B. Waller (2007). Independence, radius,
and Hamiltonian paths. MATCH Commun. Math. Comput. Chem.. 58, 481-510

6

W. J. Desormeaux, T. W. Haynes and M. A. Henning (2013). Relating the annihilation number and the total domination number
of a tree. Discrete Appl. Math.. 161, 349-354

7

T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc.,
New York.

8

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (1998). Domination in Graphs: Advanced Topics. Marcel Dekker, Inc.,
New York.

9

L. Jennings (2008). New Sufficient Condition for Hamiltonian Paths. Ph.D. Dissertation, Rice University.

10

C. E. Larson and R. Pepper (2011). Graphs with equal independence
and annihilation numbers. The Electron. J. Combin., $#$P180. 18

11

O. Ore (1962). Theory of Graphs. Amer. Math. Soc. Colloq. Publ., (Amer. Math. Soc., Providence, RI). 38

12

R. Pepper (2004). Binding Independence. Ph.D. Dissertation,
University of Houston.

13

R. Pepper (2009). On the annihilation number of a graph. Recent Advances In Electrical
Engineering: Proceedings of the 15th American Conference on
Applied Mathematics. , 217-220

14

B. Reed (1996). Paths, stars and the number three. Combin. Probab. Comput.. 5, 277-295

15

D. B. West (1996). Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River, NJ.