{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:28Z","timestamp":1740144508414,"version":"3.37.3"},"reference-count":16,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,2,26]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>A dominating set of <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>) is a subset <jats:italic>S<\/jats:italic> of <jats:italic>V<\/jats:italic> such that every vertex in <jats:italic>V<\/jats:italic> \u2212 <jats:italic>S<\/jats:italic> has at least one neighbor in <jats:italic>S<\/jats:italic>. A connected dominating set of <jats:italic>G<\/jats:italic> is a dominating set whose induced subgraph is connected. The minimum cardinality of a connected dominating set is the connected domination number <jats:italic>\u03b3<jats:sub>c<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>). Let <jats:italic>\u03b4<\/jats:italic>*(<jats:italic>G<\/jats:italic>) = min{<jats:italic>\u03b4<\/jats:italic>(<jats:italic>G<\/jats:italic>), <jats:italic>\u03b4<\/jats:italic>(<jats:italic>G\u0305<\/jats:italic>)}, where <jats:italic>G\u0305<\/jats:italic> is the complement of <jats:italic>G<\/jats:italic> and <jats:italic>\u03b4<\/jats:italic>(<jats:italic>G<\/jats:italic>) is the minimum vertex degree. In this paper, we improve upon existing results by providing new Nordhaus\u2013Gaddum type results for connected domination. In particular, we show that if <jats:italic>G<\/jats:italic> and <jats:italic>G\u0305<\/jats:italic> are both connected and min{<jats:italic>\u03b3<jats:sub>c<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>), <jats:italic>\u03b3<jats:sub>c<\/jats:sub><\/jats:italic>(<jats:italic>G\u0305<\/jats:italic>)} \u2265 3, then \n$ {\\gamma }_c(G)+{\\gamma }_c(\\bar{G})\\le 4+({\\delta }^{\\mathrm{*}}(G)-1)\\left(\\frac{1}{{\\gamma }_c(G)-2}+\\frac{1}{{\\gamma }_c(\\bar{G})-2}\\right)$\n and \n$ {\\gamma }_c(G){\\gamma }_c(\\bar{G})\\le 2({\\delta }^{\\mathrm{*}}(G)-1)\\left(\\frac{1}{{\\gamma }_c(G)-2}+\\frac{1}{{\\gamma }_c(\\bar{G})-2}+\\frac{1}{2}\\right)+4$\n. Moreover, we establish accordingly results for total domination.<\/jats:p>","DOI":"10.1051\/ro\/2020025","type":"journal-article","created":{"date-parts":[[2020,2,28]],"date-time":"2020-02-28T19:50:35Z","timestamp":1582919435000},"page":"S853-S862","source":"Crossref","is-referenced-by-count":0,"special_numbering":"Supplement","title":["Nordhaus\u2013Gaddum type results for connected and total domination"],"prefix":"10.1051","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2981-3625","authenticated-orcid":false,"given":"Rana","family":"Khoeilar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hossein","family":"Karami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mustapha","family":"Chellali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2298-4744","authenticated-orcid":false,"given":"Seyed Mahmoud","family":"Sheikholeslami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lutz","family":"Volkmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.dam.2011.12.018","volume":"161","author":"Aouchiche","year":"2013","journal-title":"Discrete Appl. Math"},{"key":"R2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/jgt.20000","volume":"46","author":"Archdeacon","year":"2004","journal-title":"J. Graph Theory"},{"key":"R3","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1002\/net.3230100304","volume":"10","author":"Cockayne","year":"1980","journal-title":"Networks"},{"key":"R4","doi-asserted-by":"crossref","first-page":"2925","DOI":"10.1016\/j.dam.2013.06.023","volume":"161","author":"Desormeauxa","year":"2013","journal-title":"Discrete Appl. Math"},{"key":"R5","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1002\/(SICI)1097-0118(200005)34:1<9::AID-JGT2>3.0.CO;2-O","volume":"34","author":"Favaron","year":"2000","journal-title":"J. Graph Theory"},{"key":"R6","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10878-009-9224-y","volume":"21","author":"Favaron","year":"2011","journal-title":"J. Comb. Optim"},{"key":"R7","first-page":"115","volume":"44","author":"Haynes","year":"2003","journal-title":"J Combin. Math. Combin. Comput"},{"unstructured":"Hedetniemi S.T. and Laskar R.C., Connected domination in graphs, edited by Bollob\u00e1s B.. In: Graph Theory and Combinatorics. Academic Press, London (1984).","key":"R8"},{"key":"R9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F","volume":"35","author":"Henning","year":"2000","journal-title":"J. Graph Theory"},{"key":"R10","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1016\/j.aml.2011.01.011","volume":"24","author":"Henning","year":"2011","journal-title":"Appl. Math. Lett"},{"key":"R11","first-page":"321","volume":"102","author":"Karami","year":"2011","journal-title":"Ars Comb"},{"key":"R12","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s00373-011-1028-z","volume":"28","author":"Karami","year":"2012","journal-title":"Graphs Comb"},{"key":"R13","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s10878-019-00383-4","volume":"38","author":"Karami","year":"2019","journal-title":"J. Comb. Optim"},{"key":"R14","first-page":"223","volume":"72","author":"Lam","year":"2007","journal-title":"Util. Math"},{"key":"R15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.2307\/2306658","volume":"63","author":"Nordhaus","year":"1956","journal-title":"Am. Math. Mon"},{"key":"R16","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s00493-007-2020-3","volume":"27","author":"Thomass\u00e9","year":"2007","journal-title":"Combinatorica"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020025\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T19:53:37Z","timestamp":1615233217000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":16,"alternative-id":["ro190309"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2020025","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021]]}}}