{"entities":{"Q456341":{"pageid":458108,"ns":120,"title":"Item:Q456341","lastrevid":51581360,"modified":"2026-01-18T21:34:11Z","type":"item","id":"Q456341","labels":{"en":{"language":"en","value":"Roman domination number of the Cartesian products of paths and cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6098361"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456341$61E2EA56-917C-4A9D-BD33-798299A2043D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c5bc662fc139865f1bb312161b841debcaef2e2","datavalue":{"value":{"text":"Roman domination number of the Cartesian products of paths and cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q456341$A6090132-1836-4AF7-8B4C-E66FC28BB58D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"974586387e8cf4a0045a3578cf35f770de1a5aa8","datavalue":{"value":"1252.05167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$983D5E63-400B-41D1-BC17-AEABB8B6E3C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5028a226efcc27d62a1ab4652ad197fff23670d1","datavalue":{"value":{"entity-type":"item","numeric-id":442219,"id":"Q442219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456341$4EC46105-0E4A-4DAD-9782-A66F3CB04BC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88a2fd89e080aa8c20a8fec4304c5082882836fd","datavalue":{"value":{"entity-type":"item","numeric-id":186164,"id":"Q186164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456341$13C1B3B2-EFFC-4A40-9E24-A709F1677865","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456341$A93F5E48-2009-414B-9149-3E0929E97F89","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ee92d50481ed05c06549abf63f6ece88b90dd74","datavalue":{"value":{"time":"+2012-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q456341$4EAB0F61-9E5E-4815-87B7-946D3EF4338B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86dfe7916be2f527eefcc9c0651122c53bb3517d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p19","type":"string"},"datatype":"url"},"type":"statement","id":"Q456341$0F1CCD1D-E2D8-4045-9EEA-8D96432FE9BA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a75fcad22a68c717845cd57de7a5f411d3bdfb71","datavalue":{"value":"Summary: Roman domination is an historically inspired variety of domination in graphs, in which vertices are assigned a value from the set \\(\\{0,1,2\\}\\) in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment.    Using an algebraic approach we present an \\(O(C)\\)-time algorithm for computing the Roman domination numbers of special classes of graphs called polygraphs, which include rotagraphs and fasciagraphs. Using this algorithm we determine formulas for the Roman domination numbers of the Cartesian products of the form \\(P_n\\square P_k\\), \\(P_n\\square C_k\\), for \\(k\\leq8\\) and \\(n \\in {\\mathbb N}\\), and \\(C_n\\square P_k\\) and \\(C_n\\square C_k\\), for \\(k\\leq 6\\) and \\(n \\in {\\mathbb N}\\), for paths \\(P_n\\) and cycles \\(C_n\\). We also find all special graphs called Roman graphs in these families of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q456341$716E119C-341B-4C28-8599-54DD4CB85312","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$1B161A35-783E-4E20-8552-D3D2B91AED25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$71DEEA62-B203-4164-8E27-9C2C601D4242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$FFEB30D7-5DF4-4616-9831-858D2832EF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$AFAFF11A-DD57-4A7C-9E32-CB2BB33A5809","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8111a4ef43c5d290a2c9e50ea936ea5836c22c0f","datavalue":{"value":"6098361","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$0A4FB3BB-0E5C-49CE-B13A-88EBF81D2895","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b620df2c564b429266e218c2fe3516ccbbbb35e7","datavalue":{"value":"Roman domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q456341$721189CE-305A-4AA1-BA28-6BF8EF30E7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7642d8b032ac6ec79fcbf380f24fdc21e9f421e","datavalue":{"value":"Cartesian product","type":"string"},"datatype":"string"},"type":"statement","id":"Q456341$1CA79EA0-29FE-41CF-8129-2A206C953542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"619bb2f2748d3996456079bf9ca2f2bb477e6039","datavalue":{"value":"polygraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q456341$49CE7857-AE48-4666-A1D1-94E9DF6C5598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q456341$C6BD0D6B-6160-4008-9413-B936D983473D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456341$6DA617F8-BE15-4EAD-8A38-D701B512177B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a550f2c0035ffa0f23427e2848a1b5b3f9f94abe","datavalue":{"value":"bafkreidmw7baplkh7u3ppbf7j4jjhfmiozwxsavnv3dwgl4mlafz4jb7sa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456341$281BA229-A7C9-4618-967C-5D4C363AD0C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fcf2f815f4416d129d7c7d9cf555520b62811cb","datavalue":{"value":{"entity-type":"item","numeric-id":1024464,"id":"Q1024464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c61273e0435ce8fef83da88ab88e6ca58e03dab","datavalue":{"value":{"amount":"+0.8469696640968323","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456341$339B7C25-CD6F-49EA-832D-649EC5BAB0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3460d9c09809fb8fe275f697adff8a704023db9","datavalue":{"value":{"entity-type":"item","numeric-id":2975269,"id":"Q2975269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54a9d01954a3e893f2ae9689e108c56335cfddfe","datavalue":{"value":{"amount":"+0.8434152603149414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456341$FDE86D4B-AF20-452D-8A1F-057A797621C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8e1d0a531220bd92c53bab8cbb1fe6f7c60bd28","datavalue":{"value":{"entity-type":"item","numeric-id":5420870,"id":"Q5420870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ece4927f67c09d3b08658c9339d5afe767a7a1f","datavalue":{"value":{"amount":"+0.8422359824180603","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456341$24C58AC0-9CD7-49FA-88CC-B0F5695BB26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646b86f8ec75540429c4b71276a3713912f5f615","datavalue":{"value":{"entity-type":"item","numeric-id":2966436,"id":"Q2966436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"450759d0d37ab05693e0d370ba6cd60d0de2ee50","datavalue":{"value":{"amount":"+0.8421614170074463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456341$87453742-17CA-4B4C-988C-3C9B4E9F0D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11c9db07640f22826e81e92508a874f35636626e","datavalue":{"value":{"entity-type":"item","numeric-id":5259399,"id":"Q5259399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff4971fa2843ae76d8c19f908da75b2b303cf395","datavalue":{"value":{"amount":"+0.8402597904205322","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456341$E7219112-120C-4C89-AC13-431093829539","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:456341","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:456341"}}}}}