Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418435 | Discrete Applied Mathematics | 2012 | 7 Pages |
Abstract
A Roman dominating function of a graph G=(V,E)G=(V,E) is a function f:V→{0,1,2}f:V→{0,1,2} such that every vertex with f(v)=0f(v)=0 is adjacent to some vertex with f(v)=2f(v)=2. The Roman domination number of GG is the minimum of w(f)=∑v∈Vf(v)w(f)=∑v∈Vf(v) over all such functions. Using a new concept of the so-called dominating couple we establish the Roman domination number of the lexicographic product of graphs. We also characterize Roman graphs among the lexicographic product of graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tadeja Kraner Šumenjak, Polona Pavlič, Aleksandra Tepeh,