{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:16Z","timestamp":1753889776605,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Graph Theory","license":[{"start":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T00:00:00Z","timestamp":1565568000000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T00:00:00Z","timestamp":1565568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T00:00:00Z","timestamp":1565568000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>The satisfiability problem is known to be $\\mathbf{NP}$-complete in general and for many restricted cases. One way to restrict instances of $k$-SAT is to limit the number of times a variable can be occurred. It was shown that for an instance of 4-SAT with the property that every variable appears in exactly 4 clauses (2 times negated and 2 times not negated), determining whether there is an assignment for variables such that every clause contains exactly two true variables and two false variables is $\\mathbf{NP}$-complete. In this work, we show that deciding the satisfiability of 3-SAT with the property that every variable appears in exactly four clauses (two times negated and two times not negated), and each clause contains at least two distinct variables is $ \\mathbf{NP} $-complete. We call this problem $(2\/2\/3)$-SAT. For an $r$-regular graph $G = (V,E)$ with $r\\geq 3$, it was asked in [Discrete Appl. Math., 160(15):2142--2146, 2012] to determine whether for a given independent set $T $ there is an independent dominating set $D$ that dominates $T$ such that $ T \\cap D =\\varnothing $? As an application of $(2\/2\/3)$-SAT problem we show that for every $r\\geq 3$, this problem is $ \\mathbf{NP} $-complete. Among other results, we study the relationship between 1-perfect codes and the incidence coloring of graphs and as another application of our complexity results, we prove that for a given cubic graph $G$ deciding whether $G$ is 4-incidence colorable is $ \\mathbf{NP} $-complete.<\/jats:p>","DOI":"10.23638\/dmtcs-21-4-9","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:38:20Z","timestamp":1743698300000},"source":"Crossref","is-referenced-by-count":0,"title":["$(2\/2\/3)$-SAT problem and its applications in dominating set problems"],"prefix":"10.23638","volume":"vol. 21 no. 4","author":[{"given":"Arash","family":"Ahadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Dehghan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2019,8,12]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1605.01319v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1605.01319v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:38:20Z","timestamp":1743698300000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/1464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,12]]},"references-count":0,"journal-issue":{"issue":"Graph Theory","published-online":{"date-parts":[[2019,8,12]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-21-4-9","relation":{"has-preprint":[{"id-type":"arxiv","id":"1605.01319v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1605.01319v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1605.01319","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1605.01319","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2019,8,12]]},"article-number":"1464"}}