Double Roman graphs in P(3k,k)

Zehui Shao (Author), Rija Erveš (Author), Huiqin Jiang (Author), Aljoša Peperko (Author), Pu Wu (Author), Janez Žerovnik (Author)

Abstract

A double Roman dominating function on a graph G=(V,E) is a function f:V->{0,1,2,3} with the properties that if f(u)=0, then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if f(u)=1, then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w(f)=[sum]v[is an element of]Vf(v). The double Roman domination number [gamma]dR(G) of a graph G is the minimum weight of a double Roman dominating function of G. A graph is said to be double Roman if [gamma]dR(G)=3[gamma](G), where [gamma](G) is the domination number of G. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs P(3k,k), and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs P(3k,k). This implies that P(3k,k) is a double Roman graph if and only if either k[identical to]0 (mod 3) or k[is an element of]{1,4}.

Keywords

dvojna rimska dominacija;posplošeni Petersenovi grafi;dvojno rimski grafi;double Roman domination;generalized Petersen graph;double Roman graph;

Data

Language:	English
Year of publishing:	2021
Typology:	1.01 - Original Scientific Article
Organization:	UL FS - Faculty of Mechanical Engineering
UDC:	519.17(045)
COBISS:	50563587
ISSN:	2227-7390
Views:	151
Downloads:	49
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	dvojna rimska dominacija;posplošeni Petersenovi grafi;dvojno rimski grafi;
Type (COBISS):	Article
Pages:	f. 1-18
Volume:	ǂVol. ǂ9
Issue:	ǂiss. ǂ4
Chronology:	Feb. 2021
DOI:	10.3390/math9040336
ID:	14305986