Name
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 gamma dR(G) >= (3n/Delta(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 not equivalent to 2 (mod 4) and DP(n, 1) is double Roman if and only if n (math) 0 (mod 4). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ACCESS.2018.2876460 | IEEE ACCESS |
Keywords | Field | DocType |
Discharging approach,double Roman domination,generalized Petersen graph,double generalized Petersen graph,double Roman graph | Discharging method,Graph,Combinatorics,Vertex (geometry),Computer science,Four color theorem,Generalized Petersen graph,Connectivity,Planar graph,Distributed computing,Graph coloring | Journal |
Volume | ISSN | Citations |
6 | 2169-3536 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zehui Shao | 1 | 119 | 30.98 |
| Pu Wu | 2 | 2 | 2.79 |
| huiqin jiang | 3 | 3 | 3.83 |
| Zepeng Li | 4 | 20 | 9.07 |
| Janez Žerovnik | 5 | 223 | 25.71 |
| Xiujun Zhang | 6 | 159 | 18.75 |