Properties of double roman domination on cardinal products of graphs

Ana Klobučar, Antoaneta Klobučar

Abstract


Double Roman domination is a stronger version of Roman domination that doubles the protection. The areas now have 0, 1, 2 or 3 legions. Every attacked area needs 2 legions for its defence, either their own, or borrowed from 1 or 2 neighbouring areas, which still have to keep at least 1 legion to themselves. The minimal number of legions in all areas together is equal to the double Roman domination number.

In this paper we determine an upper bound and a lower bound for double Roman domination numbers on cardinal product of any two graphs. Also we determine the exact values of double Roman domination numbers on P2 × G (for many types of graph G). Also, the double Roman domination number is found for P2 × Pn, P3 × Pn, P4 × Pn, while upper and lower bounds are given for P5 × Pn and P6 × Pn.

Finally, we will give a case study to determine the efficiency of double protection. We will compare double Roman domination versus Roman domination by running a simulation of a battle.


Keywords


Roman domination, Double Roman domination, Cardinal products of graphs, paths, cycles

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.2022.44a

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications