{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T19:49:33Z","timestamp":1779306573241,"version":"3.51.4"},"reference-count":23,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T00:00:00Z","timestamp":1623110400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>This paper is devoted to the study of the quasi-total strong differential of a graph, and it is a contribution to the Special Issue \u201cTheoretical computer science and discrete mathematics\u201d of Symmetry. Given a vertex x\u2208V(G) of a graph G, the neighbourhood of x is denoted by N(x). The neighbourhood of a set X\u2286V(G) is defined to be N(X)=\u22c3x\u2208XN(x), while the external neighbourhood of X is defined to be Ne(X)=N(X)\u2216X. Now, for every set X\u2286V(G) and every vertex x\u2208X, the external private neighbourhood of x with respect to X is defined as the set Pe(x,X)={y\u2208V(G)\u2216X:N(y)\u2229X={x}}. Let Xw={x\u2208X:Pe(x,X)\u2260\u2300}. The strong differential of X is defined to be \u2202s(X)=|Ne(X)|\u2212|Xw|, while the quasi-total strong differential of G is defined to be \u2202s*(G)=max{\u2202s(X):X\u2286V(G)andXw\u2286N(X)}. We show that the quasi-total strong differential is closely related to several graph parameters, including the domination number, the total domination number, the 2-domination number, the vertex cover number, the semitotal domination number, the strong differential, and the quasi-total Italian domination number. As a consequence of the study, we show that the problem of finding the quasi-total strong differential of a graph is NP-hard.<\/jats:p>","DOI":"10.3390\/sym13061036","type":"journal-article","created":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T21:16:58Z","timestamp":1623187018000},"page":"1036","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["From the Quasi-Total Strong Differential to Quasi-Total Italian Domination in Graphs"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2806-4842","authenticated-orcid":false,"given":"Abel","family":"Cabrera Mart\u00ednez","sequence":"first","affiliation":[{"name":"Departament d\u2019Enginyeria Inform\u00e0tica i Matem\u00e0tiques, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9767-2177","authenticated-orcid":false,"given":"Alejandro","family":"Estrada-Moreno","sequence":"additional","affiliation":[{"name":"Departament d\u2019Enginyeria Inform\u00e0tica i Matem\u00e0tiques, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9082-7647","authenticated-orcid":false,"given":"Juan Alberto","family":"Rodr\u00edguez-Vel\u00e1zquez","sequence":"additional","affiliation":[{"name":"Departament d\u2019Enginyeria Inform\u00e0tica i Matem\u00e0tiques, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,8]]},"reference":[{"key":"ref_1","first-page":"161","article-title":"Generalised domination and independence in graphs","volume":"123","author":"Goddard","year":"1997","journal-title":"Congr. Numer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.dam.2017.08.005","article-title":"On the differential and Roman domination number of a graph with minimum degree two","volume":"232","author":"Bermudo","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"155","DOI":"10.2298\/AADM140210003B","article-title":"The differential and the Roman domination number of a graph","volume":"8","author":"Bermudo","year":"2014","journal-title":"Appl. Anal. Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/j.endm.2014.08.037","article-title":"Relations between the differential and parameters in graphs","volume":"46","author":"Bermudo","year":"2014","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Cabrera Mart\u00ednez, A., and Rodr\u00edguez-Vel\u00e1zquez, J.A. (2021). On the perfect differential of a graph. Quaest. Math.","DOI":"10.1007\/s00025-021-01473-8"},{"key":"ref_6","first-page":"43","article-title":"Differentials in graphs","volume":"69","author":"Lewis","year":"2006","journal-title":"Util. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.5556\/j.tkjm.41.2010.664","article-title":"Differentials in certain classes of graphs","volume":"41","author":"Pushpam","year":"2010","journal-title":"Tamkang J. Math."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cabrera Mart\u00ednez, A., and Rodr\u00edguez-Vel\u00e1zquez, J.A. (2021). From the strong differential to Italian domination in graphs. Mediterr. J. Math., accepted.","DOI":"10.1007\/s00009-021-01866-7"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cabrera Mart\u00ednez, A., Puertas, M.L., and Rodr\u00edguez-Velazquez, J.A. (arXiv, 2021). On the 2-packing differential of a graph, arXiv.","DOI":"10.1007\/s00025-021-01473-8"},{"key":"ref_10","first-page":"545","article-title":"Topics in Domination in Graphs","volume":"Volume 64","author":"Haynes","year":"2020","journal-title":"Developments in Mathematics"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Fundamentals of Domination in Graphs, Marcel Dekker Inc.","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"ref_12","unstructured":"Haynes, T., Hedetniemi, S., and Slater, P. (1998). Domination in Graphs: Volume 2: Advanced Topics, Taylor & Francis."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Henning, M.A., and Yeo, A. (2013). Total Domination in Graphs, Springer.","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1155\/S016117129000031X","article-title":"A note on the k-domination number of a graph","volume":"13","author":"Caro","year":"1990","journal-title":"Int. J. Math. Math. Sci."},{"key":"ref_15","first-page":"67","article-title":"Semitotal domination in graphs","volume":"94","author":"Goddard","year":"2014","journal-title":"Util. Math."},{"key":"ref_16","first-page":"133","article-title":"\u00dcber extreme Punkt- und Kantenmengen","volume":"2","author":"Gallai","year":"1959","journal-title":"Ann. Univ. Sci. Budapestinensis Rolando E\u00f6tv\u00f6s Nomin. Sect. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/BF01844162","article-title":"On the corona of two graphs","volume":"4","author":"Frucht","year":"1970","journal-title":"Aequationes Math."},{"key":"ref_18","unstructured":"Fink, J.F., and Jacobson, M.S. (1985). n-domination in graphs. Graph Theory with Applications to Algorithms and Computer Science, Wiley-Interscience Publication Wiley."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","article-title":"Roman domination in graphs","volume":"278","author":"Cockayne","year":"2004","journal-title":"Discret. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s00025-019-1097-5","article-title":"Quasi-total Roman domination in graphs","volume":"74","author":"Yero","year":"2019","journal-title":"Results Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","article-title":"Roman {2}-domination","volume":"204","author":"Chellali","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.dam.2016.09.035","article-title":"Italian domination in trees","volume":"217","author":"Henning","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_23","first-page":"125","article-title":"Roman, Italian, and 2-domination","volume":"108","author":"Klostermeyer","year":"2019","journal-title":"J. Combin. Math. Combin. Comput."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/1036\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:12:15Z","timestamp":1760163135000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/1036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,8]]},"references-count":23,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["sym13061036"],"URL":"https:\/\/doi.org\/10.3390\/sym13061036","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,8]]}}}