Double Roman Domination in Generalized Petersen Graphs P(ck, k)

Symmetry

Darja Rupnik Poklukar¹  Janez Žerovnik¹ 

[1] Faculty of Mechanical Engineering, University of Ljubljana, Aškerčeva 6, 1000 Ljubljana, Slovenia;

关键词: double Roman domination;    generalized Petersen graph;    graph cover;   

DOI  :  10.3390/sym14061121

来源: DOAJ

【 摘 要 】

A double Roman dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2,3\}$, satisfying the condition that every vertex u for which $f\left(u\right)=1$ is adjacent to at least one vertex assigned 2 or 3, and every vertex u with $f\left(u\right)=0$ is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2. The weight of f equals the sum $w\left(f\right)={\sum }_{v\in V}f\left(v\right)$. The minimum weight of a double Roman dominating function of G is called the double Roman domination number ${\gamma }_{dR}\left(G\right)$ of a graph G. We obtain tight bounds and in some cases closed expressions for the double Roman domination number of generalized Petersen graphs $P(ck,k)$. In short, we prove that ${\gamma }_{dR}\left(P(ck,k)\right)=\frac{3}{2}ck+\epsilon$, where ${\displaystyle \underset{c\to \infty ,k\to \infty }{lim}\frac{\epsilon }{ck}=0}$.

【 授权许可】

Unknown