Nordhaus–Gaddum type results for connected and total domination

Khoeilar, Rana; Karami, Hossein; Chellali, Mustapha; Sheikholeslami, Seyed Mahmoud; Volkmann, Lutz

doi:10.1051/ro/2020025

Khoeilar, Rana ; Karami, Hossein ; Chellali, Mustapha ; Sheikholeslami, Seyed Mahmoud ; Volkmann, Lutz

RAIRO. Operations Research, Tome 55 (2021), pp. S853-S862

Résumé

A dominating set of G = (V, E) is a subset S of V such that every vertex in V − S has at least one neighbor in S. A connected dominating set of G is a dominating set whose induced subgraph is connected. The minimum cardinality of a connected dominating set is the connected domination number $$(G). Let δ*(G) = min{δ(G), δ(G̅)}, where G̅ is the complement of G and δ(G) is the minimum vertex degree. In this paper, we improve upon existing results by providing new Nordhaus–Gaddum type results for connected domination. In particular, we show that if G and G̅ are both connected and min{$$(G), $$(G̅)} ≥ 3, then $γ_{c} (G) + γ_{c} (\bar{G}) \leq 4 + (δ^{*} (G) - 1) (\frac{1}{γ_{c} (G) - 2} + \frac{1}{γ_{c} (\bar{G}) - 2})$ and $γ_{c} (G) γ_{c} (\bar{G}) \leq 2 (δ^{*} (G) - 1) (\frac{1}{γ_{c} (G) - 2} + \frac{1}{γ_{c} (\bar{G}) - 2} + \frac{1}{2}) + 4$ . Moreover, we establish accordingly results for total domination.

MR Zbl

DOI : 10.1051/ro/2020025

Classification : 05C69
Keywords: Connected domination number, total domination number, Nordhaus–Gaddum type result

@article{RO_2021__55_S1_S853_0,
     author = {Khoeilar, Rana and Karami, Hossein and Chellali, Mustapha and Sheikholeslami, Seyed Mahmoud and Volkmann, Lutz},
     title = {Nordhaus{\textendash}Gaddum type results for connected and total domination},
     journal = {RAIRO. Operations Research},
     pages = {S853--S862},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020025},
     mrnumber = {4223144},
     zbl = {1469.05133},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020025/}
}

TY  - JOUR
AU  - Khoeilar, Rana
AU  - Karami, Hossein
AU  - Chellali, Mustapha
AU  - Sheikholeslami, Seyed Mahmoud
AU  - Volkmann, Lutz
TI  - Nordhaus–Gaddum type results for connected and total domination
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S853
EP  - S862
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020025/
DO  - 10.1051/ro/2020025
LA  - en
ID  - RO_2021__55_S1_S853_0
ER  -

%0 Journal Article
%A Khoeilar, Rana
%A Karami, Hossein
%A Chellali, Mustapha
%A Sheikholeslami, Seyed Mahmoud
%A Volkmann, Lutz
%T Nordhaus–Gaddum type results for connected and total domination
%J RAIRO. Operations Research
%D 2021
%P S853-S862
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020025/
%R 10.1051/ro/2020025
%G en
%F RO_2021__55_S1_S853_0

Khoeilar, Rana; Karami, Hossein; Chellali, Mustapha; Sheikholeslami, Seyed Mahmoud; Volkmann, Lutz. Nordhaus–Gaddum type results for connected and total domination. RAIRO. Operations Research, Tome 55 (2021), pp. S853-S862. doi: 10.1051/ro/2020025

Bibliographie
Cité par

M. Aouchiche and P. Hansen, A survey of Nordhaus–Gaddum type relations. Discrete Appl. Math. 161 (2013) 466–546. | MR | Zbl | DOI

D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P. C. B. Lam, S. Seager, B. Wei and R. Yuster, Some remarks on domination. J. Graph Theory 46 (2004) 207–210. | MR | Zbl | DOI

E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs. Networks 10 (1980) 211–219. | MR | Zbl | DOI

W. J. Desormeaux, T. W. Haynes and M. A. Henning, Bounds on the connected domination number of a graph. Discrete Appl. Math. 161 (2013) 2925–2931. | MR | Zbl | DOI

O. Favaron, M. A. Henning, C. M. Mynhardt and J. Puech, Total domination in graphs with minimum degree three. J. Graph Theory 34 (2000) 9–19. | MR | Zbl | DOI

O. Favaron, H. Karami and S. M. Sheikholeslami, Bounding the total subdivision number of a graph in terms of its order. J. Comb. Optim. 21 (2011) 209–218. | MR | Zbl | DOI

T. W. Haynes, S. T. Hedetniemi and L. C. Van Der Merwe, Total domination subdivision numbers. J Combin. Math. Combin. Comput. 44 (2003) 115–128. | MR | Zbl

S. T. Hedetniemi and R. C. Laskar, Connected domination in graphs, edited by B. Bollobás. In: Graph Theory and Combinatorics. Academic Press, London (1984). | MR | Zbl

M. A. Henning, Graphs with large total domination number. J. Graph Theory 35 (2000) 21–45. | MR | Zbl | DOI

M. A. Henning, E. J. Joubert and J. Southey, Nordhaus–Gaddum bounds for total domination. Appl. Math. Lett. 24 (2011) 987–990. | MR | Zbl | DOI

H. Karami, A. Khodkar and S. M. Sheikholeslami, An upper bound on total domination subdivision number. Ars Comb. 102 (2011) 321–331. | MR | Zbl

H. Karami, A. Khodkar, S. M. Sheikholeslami, D. B. West, Connected domination number of a graph and its complement. Graphs Comb. 28 (2012) 123–131. | MR | Zbl | DOI

H. Karami, R. Khoeilar and S. M. Sheikholeslami, On two conjectures concerning total domination subdivision number in graphs. J. Comb. Optim. 38 (2019) 333–340. | MR | Zbl | DOI

P. C. B. Lam and B. Wei, On the total domination number of graphs. Util. Math. 72 (2007) 223–240. | MR | Zbl

E. A. Nordhaus and J. W. Gaddum, On complementary graphs. Am. Math. Mon. 63 (1956) 175–177. | MR | Zbl | DOI

S. Thomassé and A. Yeo, Total domination of graphs and small transversals of hypergraphs. Combinatorica 27 (2007) 473–487. | MR | Zbl | DOI

Cité par Sources :