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

Document Type : Research Paper

Authors

1 Azarbaijan Shahid Madani University

2 Azarbaijan University of Tarbiat Moallem

Abstract

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‎.

Keywords

Main Subjects

References

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. Y. Caro and R. Pepper (2012). Degree Sequence Index Strategy. arXiv:1210.1805v1. 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. 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 E. DeLaVina, R. Pepper and B. Waller (2007). Independence, radius, and Hamiltonian paths. MATCH Commun. Math. Comput. Chem.. 58, 481-510 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 T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (1998). Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York. L. Jennings (2008). New Sufficient Condition for Hamiltonian Paths. Ph.D. Dissertation, Rice University. C. E. Larson and R. Pepper (2011). Graphs with equal independence and annihilation numbers. The Electron. J. Combin., $\#$P180. 18 O. Ore (1962). Theory of Graphs. Amer. Math. Soc. Colloq. Publ., (Amer. Math. Soc., Providence, RI). 38 R. Pepper (2004). Binding Independence. Ph.D. Dissertation, University of Houston. 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 B. Reed (1996). Paths, stars and the number three. Combin. Probab. Comput.. 5, 277-295 D. B. West (1996). Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River, NJ.

Files

History

  • Receive Date: 26 July 2012
  • Revise Date: 18 February 2013
  • Accept Date: 23 February 2013
  • Published Online: 01 March 2013

Share

How to cite

Statistics