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

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

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

2 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

Articles in Press, Accepted Manuscript
Available Online from 15 April 2026

Files

Share

How to cite

Statistics