{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:39:15Z","timestamp":1756312755272,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T00:00:00Z","timestamp":1603843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T00:00:00Z","timestamp":1603843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006190","name":"Gdansk University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006190","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,1]]},"abstract":"Abstract<\/jats:title>An Italian dominating function (IDF) on a graph G<\/jats:italic> is a function $$f:V(G)\\rightarrow \\{0,1,2\\}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2192<\/mml:mo>\n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that for every vertex v<\/jats:italic> with $$f(v)=0$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the total weight of f<\/jats:italic> assigned to the neighbours of v<\/jats:italic> is at least two, i.e., $$\\sum _{u\\in N_G(v)}f(u)\\ge 2$$<\/jats:tex-math>\n \n \n \u2211<\/mml:mo>\n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n \n N<\/mml:mi>\n G<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msub>\n f<\/mml:mi>\n \n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For any function $$f:V(G)\\rightarrow \\{0,1,2\\}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2192<\/mml:mo>\n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and any pair of adjacent vertices with $$f(v) = 0$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and u<\/jats:italic> with $$f(u) > 0$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the function $$f_{u\\rightarrow v}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n u<\/mml:mi>\n \u2192<\/mml:mo>\n v<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is defined by $$f_{u\\rightarrow v}(v)=1$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n u<\/mml:mi>\n \u2192<\/mml:mo>\n v<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$f_{u\\rightarrow v}(u)=f(u)-1$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n u<\/mml:mi>\n \u2192<\/mml:mo>\n v<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n f<\/mml:mi>\n \n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$f_{u\\rightarrow v}(x)=f(x)$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n u<\/mml:mi>\n \u2192<\/mml:mo>\n v<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n f<\/mml:mi>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> whenever $$x\\in V(G){\\setminus }\\{u,v\\}$$<\/jats:tex-math>\n \n x<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \\<\/mml:mo>\n {<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A secure Italian dominating function on a graph G<\/jats:italic> is defined as an IDF f<\/jats:italic> which satisfies that for every vertex v<\/jats:italic> with $$f(v)=0$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, there exists a neighbour u<\/jats:italic> with $$f(u)>0$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that $$f_{u\\rightarrow v}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n u<\/mml:mi>\n \u2192<\/mml:mo>\n v<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is an IDF. The weight of f<\/jats:italic> is $$\\omega (f)=\\sum _{v\\in V(G) }f(v)$$<\/jats:tex-math>\n \n \u03c9<\/mml:mi>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n f<\/mml:mi>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The minimum weight among all secure Italian dominating functions on G<\/jats:italic> is the secure Italian domination number of G<\/jats:italic>. This paper is devoted to initiating the study of the secure Italian domination number of a graph. In particular, we prove that the problem of finding this parameter is NP-hard and we obtain general bounds on it. Moreover, for certain classes of graphs, we obtain closed formulas for this novel parameter.<\/jats:p>","DOI":"10.1007\/s10878-020-00658-1","type":"journal-article","created":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T06:02:47Z","timestamp":1603864967000},"page":"56-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Secure Italian domination in graphs"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7296-1893","authenticated-orcid":false,"given":"M.","family":"Dettlaff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Lema\u0144ska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. A.","family":"Rodr\u00edguez-Vel\u00e1zquez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,28]]},"reference":[{"issue":"2","key":"658_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.2989\/QM.2008.31.2.5.477","volume":"31","author":"AP Burger","year":"2008","unstructured":"Burger AP, Henning MA, van Vuuren JH (2008) Vertex covers and secure domination in graphs. Quaest Math 31(2):163\u2013171","journal-title":"Quaest Math"},{"key":"658_CR2","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.dam.2014.06.016","volume":"178","author":"M Chellali","year":"2014","unstructured":"Chellali M, Haynes TW, Hedetniemi ST (2014) Bounds on weak Roman and 2-rainbow domination numbers. Discrete Appl Math 178:27\u201332","journal-title":"Discrete Appl Math"},{"key":"658_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","volume":"204","author":"M Chellali","year":"2016","unstructured":"Chellali M, Haynes TW, Hedetniemi ST, McRae AA (2016) Roman 2-domination. Discrete Appl Math 204:22\u201328","journal-title":"Discrete Appl Math"},{"key":"658_CR4","first-page":"87","volume":"39","author":"EJ Cockayne","year":"2003","unstructured":"Cockayne EJ, Favaron O, Mynhardt CM (2003) Secure domination, weak Roman domination and forbidden subgraphs. Bull Inst Comb Appl 39:87\u2013100","journal-title":"Bull Inst Comb Appl"},{"issue":"1\u20133","key":"658_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne EJ, Dreyer PA Jr, Hedetniemi SM, Hedetniemi ST (2004) Roman domination in graphs. Discrete Math 278(1\u20133):11\u201322","journal-title":"Discrete Math"},{"key":"658_CR6","first-page":"19","volume":"67","author":"EJ Cockayne","year":"2005","unstructured":"Cockayne EJ, Grobler PJP, Gr\u00fcndlingh WR, Munganga J, van Vuuren JH (2005) Protection of a graph. Util Math 67:19\u201332","journal-title":"Util Math"},{"key":"658_CR7","volume-title":"Domination in graphs: volume 2: advanced topics","author":"T Haynes","year":"1998","unstructured":"Haynes T, Hedetniemi S, Slater P (1998a) Domination in graphs: volume 2: advanced topics. Chapman & Hall\/CRC Pure and Applied Mathematics, Taylor & Francis, Routledge"},{"key":"658_CR8","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998b) Fundamentals of domination in graphs. Chapman and Hall\/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc., New York"},{"issue":"1\u20133","key":"658_CR9","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"MA Henning","year":"2003","unstructured":"Henning MA, Hedetniemi ST (2003) Defending the Roman Empire\u2014a new strategy. Discrete Math 266(1\u20133):239\u2013251 (the 18th British Combinatorial Conference (Brighton, 2001))","journal-title":"Discrete Math"},{"key":"658_CR10","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.dam.2016.09.035","volume":"217","author":"MA Henning","year":"2017","unstructured":"Henning MA, Klostermeyer WF (2017) Italian domination in trees. Discrete Appl Math 217:557\u2013564","journal-title":"Discrete Appl Math"},{"key":"658_CR11","first-page":"125","volume":"108","author":"WF Klostermeyer","year":"2019","unstructured":"Klostermeyer WF, MacGillivray G (2019) Roman, Italian, and 2-domination. J Comb Math Comb Comput 108:125\u2013146","journal-title":"J Comb Math Comb Comput"},{"issue":"2","key":"658_CR12","doi-asserted-by":"publisher","first-page":"267","DOI":"10.7151\/dmgt.1405","volume":"28","author":"WF Klostermeyer","year":"2008","unstructured":"Klostermeyer WF, Mynhardt CM (2008) Secure domination and secure total domination in graphs. Discuss Math Graph Theory 28(2):267\u2013284","journal-title":"Discuss Math Graph Theory"},{"issue":"10","key":"658_CR13","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1016\/j.ipl.2015.05.006","volume":"115","author":"H Merouane","year":"2015","unstructured":"Merouane H, Chellali M (2015) On secure domination in graphs. Inf Process Lett 115(10):786\u2013790","journal-title":"Inf Process Lett"},{"issue":"6","key":"658_CR14","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"I Stewart","year":"1999","unstructured":"Stewart I (1999) Defend the Roman empire!. Sci Am 281(6):136\u2013138","journal-title":"Sci Am"},{"key":"658_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.2298\/FIL1901319V","volume":"33","author":"M Valveny","year":"2019","unstructured":"Valveny M, Rodr\u00edguez-Vel\u00e1zquez JA (2019) Protection of graphs with emphasis on cartesian product graphs. Filomat 33:319\u2013333","journal-title":"Filomat"},{"key":"658_CR16","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.dam.2018.03.039","volume":"263","author":"M Valveny","year":"2019","unstructured":"Valveny M, P\u00e9rez-Ros\u00e9s H, Rodr\u00edguez-Vel\u00e1zquez JA (2019) On the weak Roman domination number of lexicographic product graphs. Discrete Appl Math 263:257\u2013270","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00658-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-020-00658-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00658-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,24]],"date-time":"2021-01-24T03:10:21Z","timestamp":1611457821000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-020-00658-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,28]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["658"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00658-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,10,28]]},"assertion":[{"value":"29 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}