Bounds on the disjunctive domination number of a tree

Zhuang, Wei

doi:10.1051/ro/2022105

Zhuang, Wei

RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2389-2401

Résumé

A set D of vertices in a graph G is a disjunctive dominating set in G if every vertex not in D is adjacent to a vertex of D or has at least two vertices in D at distance 2 from it in G. The disjunctive domination number, $γ_{2}^{d} (G)$ , of G is the minimum cardinality of a disjunctive dominating set in G. We show that if T is a tree of order n with l leaves and s support vertices, then $\frac{n - l + 3}{4} γ_{2}^{d} (T) \leq \frac{n + l + s}{4}$ . Moreover, we characterize the families of trees which attain these bounds.

MR

DOI : 10.1051/ro/2022105

Classification : 05C05, 05C69
Keywords: Disjunctive dominating set, disjunctive domination number, tree

@article{RO_2022__56_4_2389_0,
     author = {Zhuang, Wei},
     title = {Bounds on the disjunctive domination number of a tree},
     journal = {RAIRO. Operations Research},
     pages = {2389--2401},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {4},
     doi = {10.1051/ro/2022105},
     mrnumber = {4458838},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022105/}
}

TY  - JOUR
AU  - Zhuang, Wei
TI  - Bounds on the disjunctive domination number of a tree
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 2389
EP  - 2401
VL  - 56
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022105/
DO  - 10.1051/ro/2022105
LA  - en
ID  - RO_2022__56_4_2389_0
ER  -

%0 Journal Article
%A Zhuang, Wei
%T Bounds on the disjunctive domination number of a tree
%J RAIRO. Operations Research
%D 2022
%P 2389-2401
%V 56
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022105/
%R 10.1051/ro/2022105
%G en
%F RO_2022__56_4_2389_0

Zhuang, Wei. Bounds on the disjunctive domination number of a tree. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2389-2401. doi: 10.1051/ro/2022105

Bibliographie
Cité par

[1] M. Anderson, R. C. Brigham, J. R. Carrington, R. P. Vitray and J. Yellen, On exponential domination of $C_{m} \times C_{n}$ _. AKCE Int. J. Graphs Comb. 6 (2009) 341–351. | MR

[2] P. Dankelmann, D. Day, D. Erwin, S. Mukwembi and H. Swart, Domination with exponential decay. Discrete Math. 309 (2009) 5877–5883. | MR | DOI

[3] X. Chen and M. Y. Sohn, Bounds on the locating-total domination number of a tree. Discrete Appl. Math. 159 (2011) 769–773. | MR | DOI

[4] W. Goddard, M. A. Henning and C. A. Mcpillan, The disjunctive domination number of a graph. Quaest. Math. 37 (2014) 547–561. | MR | DOI

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

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

[7] M. A. Henning, Distance domination in graphs, In Domination in Graphs: Advanced Topics, edited by T. W. Haynes, S. T. Hedetniemi and P. J. Slater. Marcel Dekker Inc., New York (1998) 335–365. | MR

[8] M. A. Henning and S. A. Marcon, Domination versus disjunctive domination in trees. Discrete Appl. Math. 184 (2015) 171–177. | MR | DOI

[9] M. A. Henning and S. A. Marcon, A constructive characterization of trees with equal total domination and disjunctive domination numbers. Quaest. Math. 39 (2016) 531–543. | MR | DOI

[10] M. A. Henning and S. A. Marcon, Domination versus disjunctive domination in graphs. Quaest. Math. 39 (2016) 261–273. | MR | DOI

[11] M. A. Henning and S. A. Marcon, Vertices contained in all or in no minimum disjunctive dominating set of a tree. Util. Math. 105 (2017) 95–123. | MR

[12] F. P. Jamil and R. P. Malalay, On disjunctive domination in graphs. Quaest. Math. 43 (2020) 149–168. | MR | DOI

[13] M. Krzywkowski, An upper bound on the 2-outer independent domination number of a tree. C. R. Math. 349 (2011) 1123–1125. | MR | DOI

[14] M. Krzywkowski, An upper bound for the double outer-independent domination number of a tree. Georgian Math. J. 22 (2015) 105–109. | MR | DOI

[15] Z. Li and J. Xu, On the trees with same signed edge and signed star domination number. Int. J. Comput. Math. 95 (2018) 2388–2395. | MR | DOI

[16] W. Ning, M. Lu and J. Guo, Bounds on the differentating-total domination number of a tree. Discrete Appl. Math. 200 (2016) 153–160. | MR | DOI

[17] W. Ning, M. Lu and K. Wang, Bounding the locating-total domination number of a tree in terms of its annihilation number. Discuss. Math. Graph Theory 39 (2019) 31–40. | MR | DOI

[18] B. S. Panda, A. Pandey and S. Paul, Algorithmic aspects of $b$ -disjunctive domination in graphs. J. Comb. Optim. 36 (2018) 572–590. | MR | DOI

[19] N. J. Rad and H. Rahbani, Bounds on the locating roman domination number in trees. Discuss. Math. Graph Theory 38 (2018) 49–62. | MR | DOI

[20] N. J. Rad and H. Rahbani, Bounds on the locating-domination number and differentating-total domination number in trees. Discuss. Math. Graph Theory 38 (2018) 455–462. | MR | DOI

[21] Y. B. Venkatakrishnan and B. Krishnakumari, An improved upper bound of edge-vertex domination number of a tree. Inform. process. Lett. 134 (2018) 14–17. | MR | DOI

[22] Y. B. Venkatakrishnan, H. N. Kumar and B. Krishnakumari, Bounds on the double edge-vertex domination number of a tree. Ars Comb. 146 (2019) 29–36. | MR

[23] K. Wang, W. Ning and M. Lu, Bounds on the locating-total domination number in trees. Discuss. Math. Graph Theory 40 (2020) 25–34. | MR | DOI

[24] H. Yang, P. Wu and S. Nazari-Moghaddam, Bounds for signed double roman $k$ -domination in trees. RAIRO: RO 53 (2019) 627–643. | MR | Zbl | Numdam | DOI

Cité par Sources :