Upper bounds for $[1,2]$-domination number in trees

Document Type : Original paper

Authors

1 Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

2 Institute for Geometry and Practical Mathematics, RWTH Aachen University, 52056 Aachen, Germany

Abstract

A set $S$ of vertices is a $[1,2]$-set of a graph $G$ if every vertex $v$ not in $S$ is adjacent to at least one but no more than two vertices in $S$. The minimum cardinality of a $[1,2]$-set is the $[1,2]$-domination number. In this paper, we present two upper bounds on the $[1,2]$-domination number of trees in terms of the order, number of support vertices and number of leaves. Furthermore, extremal trees reaching one of these two bounds are provided.

Keywords

Main Subjects

References

[1] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, and M.L. Puertas González, Perfect and quasiperfect domination in trees, Appl. Analysis Discrete Math. 10 (2016), 46–64. https://doi.org/10.2298/AADM160406007C
[2] Y. Caro, A. Hansberg, and M. Henning, Fair domination in graphs, Discrete Math. 312 (2012), 2905–2914. https://doi.org/10.1016/j.disc.2012.05.006
[3] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. McRae, $[1, 2]$-sets in graphs, Discrete Appl. Math. 161 (2013), 2885–2893.  https://doi.org/10.1016/j.dam.2013.06.012
[4] M. Livingston and Q.F. Stout, Perfect dominating sets, Congr. Numer. 79 (1990), 187–203.
Communications in Combinatorics and Optimization
Volume 11, Issue 4
Special issue in honor of Prof. Odile Favaron
December 2026
Pages 1163-1174

Files

Share

How to cite

Statistics