Geodesic
On the roman domination problem of some Johnson graphs
Filomat, Tome 37 (2023) no. 7, p. 2067

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

A Roman domination function (RDF) on a graph G with a set of vertices V = V(G) is a function f : V → {0, 1, 2} which satisfies the condition that each vertex v ∈ V such that f (v) = 0 is adjacent to at least one vertex u such that f (u) = 2. The minimum weight value of an RDF on graph G is called the Roman domination number (RDN) of G and it is denoted by γ R (G). An RDF for which γ R (G) is achieved is called a γ R (G)-function. This paper considers Roman domination problem for Johnson graphs J n,2 and J n,3. For J n,2 , n ⩾ 4 it is proved that γ R (J n,2) = n − 1. New lower and upper bounds for J n,3 , n ⩾ 6 are derived using results on the minimal coverings of pairs by triples. These bounds quadratically depend on dimension n.
DOI : 10.2298/FIL2307067Z
Classification : 05C69, 05C76
Keywords: Graph theory, Graph domination, Roman domination, Johnson graphs 
Tatjana Zec. On the roman domination problem of some Johnson graphs. Filomat, Tome 37 (2023) no. 7, p. 2067 . doi: 10.2298/FIL2307067Z
@article{10_2298_FIL2307067Z,
     author = {Tatjana Zec},
     title = {On the roman domination problem of some {Johnson} graphs},
     journal = {Filomat},
     pages = {2067 },
     year = {2023},
     volume = {37},
     number = {7},
     doi = {10.2298/FIL2307067Z},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2307067Z/}
}
TY  - JOUR
AU  - Tatjana Zec
TI  - On the roman domination problem of some Johnson graphs
JO  - Filomat
PY  - 2023
SP  - 2067 
VL  - 37
IS  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.2298/FIL2307067Z/
DO  - 10.2298/FIL2307067Z
LA  - en
ID  - 10_2298_FIL2307067Z
ER  - 
%0 Journal Article
%A Tatjana Zec
%T On the roman domination problem of some Johnson graphs
%J Filomat
%D 2023
%P 2067 
%V 37
%N 7
%U http://geodesic.mathdoc.fr/articles/10.2298/FIL2307067Z/
%R 10.2298/FIL2307067Z
%G en
%F 10_2298_FIL2307067Z

Cité par Sources :