{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:19Z","timestamp":1740133939541,"version":"3.37.3"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/100007225","name":"Ministry of Science and Technology","doi-asserted-by":"publisher","award":["MOST~104-2221-E-141 -008 -MY3"],"award-info":[{"award-number":["MOST~104-2221-E-141 -008 -MY3"]}],"id":[{"id":"10.13039\/100007225","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p> In this paper, we introduce a new variant of domination called the outer-paired domination. For a graph [Formula: see text], an outer-paired dominating set [Formula: see text] is a dominating set of [Formula: see text] such that the induced subgraph of [Formula: see text] contains a perfect matching. The outer-paired domination number of a graph [Formula: see text] is the cardinality of a minimum outer-paired dominating set of [Formula: see text]. We show that finding the outer-paired domination number of a graph [Formula: see text] is NP-hard on bipartite graphs, chordal graphs, and planar graphs. We also propose a linear-time algorithm for solving the outer-paired domination problem on trees. <\/jats:p>","DOI":"10.1142\/s0129054122500034","type":"journal-article","created":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:12:20Z","timestamp":1645182740000},"page":"141-148","source":"Crossref","is-referenced-by-count":0,"title":["The Outer-Paired Domination of Graphs"],"prefix":"10.1142","volume":"33","author":[{"given":"Chih-Yuan","family":"Lin","sequence":"first","affiliation":[{"name":"Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia-Jie","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Information Management, Shih Hsin University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue-Li","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Chung-Kung Yen","sequence":"additional","affiliation":[{"name":"Department of Information Management, Shih Hsin University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chiun-Chieh","family":"Hsu","sequence":"additional","affiliation":[{"name":"Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"key":"S0129054122500034BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9427-x"},{"key":"S0129054122500034BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90105-X"},{"key":"S0129054122500034BIB003","doi-asserted-by":"publisher","DOI":"10.11650\/twjm\/1500602498"},{"key":"S0129054122500034BIB004","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100304"},{"key":"S0129054122500034BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"S0129054122500034BIB006","first-page":"19","volume":"67","author":"Cockayne E. J.","year":"2005","journal-title":"Utility Mathematics"},{"key":"S0129054122500034BIB007","first-page":"35","volume":"38","author":"Cyman J.","year":"2007","journal-title":"The Australasian J. Combin."},{"key":"S0129054122500034BIB008","first-page":"282","volume-title":"Graph Theory with Applications to Algorithms and Computer Science","author":"Fink J. F.","year":"1985"},{"key":"S0129054122500034BIB009","first-page":"301","volume-title":"Graph Theory with Applications to Algorithms and Computer Science","author":"Fink J. F.","year":"1985"},{"volume-title":"Fundamentals of Domination in Graphs","year":"1998","author":"Haynes T. W.","key":"S0129054122500034BIB010"},{"key":"S0129054122500034BIB011","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"S0129054122500034BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00811-7"},{"key":"S0129054122500034BIB013","first-page":"265","volume":"81","author":"Jiang H.","year":"2010","journal-title":"Utilitas Mathematica"},{"key":"S0129054122500034BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.05.001"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122500034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T04:34:37Z","timestamp":1646886877000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054122500034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":14,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1142\/S0129054122500034"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122500034","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2022,2]]}}}