Discharging Approach for Double Roman Domination in Graphs

Abstract

The discharging method is most well-known for its central role in the proof of the Four Color Theorem. This proof technique was extensively applied to study various graph coloring problems, in particular on planar graphs. In this paper, we show that suitably altered discharging technique can also be used on domination-type problems. The general discharging approach for domination-type problems is illustrated on a specific domination-type problem, the double Roman domination on some generalized Petersen graphs. By applying this approach, we first prove that γdR(G)≥(3n/Δ(G) + 1) for any connected graph G with n≥2 vertices. As examples, we also determine the exact values of the double Roman domination numbers of the generalized Petersen graphs P(n, 1) and the double generalized Petersen graphs DP(n, 1). The obtained results imply that P(n, 1) is double Roman if and only if n ≠ 2 (mod 4) and DP(n, 1) is double Roman if and only if n ≡ 0 (mod 4).

Keywords

• Discharging approach
• double Roman domination
• generalized Petersen graph
• double generalized Petersen graph
• double Roman graph