{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:38:32Z","timestamp":1740155912627,"version":"3.37.3"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701236"],"award-info":[{"award-number":["11701236"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p> As a variant of minimum connected dominating set problem, two disjoint connected dominating sets (DCDS) problem is to ask whether there are two DCDS [Formula: see text] in a connected graph [Formula: see text] with [Formula: see text] and [Formula: see text], and if not, how to add an edge subset with minimum cardinality such that the new graph has a pair of DCDS. The two DCDS problem is so hard that it is NP-hard on trees. In this paper, if the vertex set [Formula: see text] of a connected graph [Formula: see text] can be partitioned into two DCDS of [Formula: see text], then it is called a DCDS graph. First, a necessary but not sufficient condition is proposed for cubic (3-regular) graph to be a DCDS graph. To be exact, if a cubic graph is a DCDS graph, there are at most four disjoint triangles in it. Next, if a connected graph [Formula: see text] is a DCDS graph, a simple but nontrivial upper bound [Formula: see text] of the girth [Formula: see text] is presented. <\/jats:p>","DOI":"10.1142\/s1793830919500654","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T04:04:57Z","timestamp":1568001897000},"page":"1950065","source":"Crossref","is-referenced-by-count":0,"title":["Some results for the two disjoint connected dominating sets problem"],"prefix":"10.1142","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3970-1798","authenticated-orcid":false,"given":"Xianliang","family":"Liu","sequence":"first","affiliation":[{"name":"College of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, P. R. China"}]},{"given":"Zishen","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Xi\u2019an Jiaotong University, Xi\u2019an 710049, P. R. China"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Xi\u2019an Jiaotong University, Xi\u2019an 710049, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"key":"S1793830919500654BIB001","first-page":"12","volume":"42","author":"Broere I.","year":"2004","journal-title":"Bull. Inst. Combin. Appl."},{"key":"S1793830919500654BIB002","doi-asserted-by":"publisher","DOI":"10.1002\/net.10097"},{"key":"S1793830919500654BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.020"},{"key":"S1793830919500654BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/1167935.1167941"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1978","author":"Garey M. R.","key":"S1793830919500654BIB005"},{"key":"S1793830919500654BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"S1793830919500654BIB007","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2754"},{"key":"S1793830919500654BIB008","first-page":"128","volume":"5","author":"Heggernes P.","year":"1998","journal-title":"Nord. J. Comput."},{"key":"S1793830919500654BIB009","unstructured":"M. Li,  P.J. Wan and  F. Yao,  Tighter approximation bounds for minimum CDS in wireless ad hoc networks,  ISAAC\u201909, LNCS 5878  (2009)  699\u2013709."},{"key":"S1793830919500654BIB010","first-page":"419","volume":"337","author":"Liu X. L.","year":"2018","journal-title":"Appl. Math. Comput."},{"key":"S1793830919500654BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.013"},{"key":"S1793830919500654BIB012","doi-asserted-by":"publisher","DOI":"10.1023\/B:MONE.0000013625.87793.13"},{"key":"S1793830919500654BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.08.037"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830919500654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T01:43:49Z","timestamp":1576806229000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830919500654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":13,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S1793830919500654"],"URL":"https:\/\/doi.org\/10.1142\/s1793830919500654","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}