We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Double Roman Domination in Graphs with Minimum Degree at Least Two and No C5-cycle.
- Authors
Kosari, Saeed; Shao, Zehui; Sheikholeslami, Seyed Mahmoud; Chellali, Mustapha; Khoeilar, Rana; Karami, Hossein
- Abstract
A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbor w with f (w) ≥ 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ dR (G) is the minimum weight of a DRDF on G. Recently, Khoeilar et al. (Discrete Appl Math 270:159–167, 2019) proved that a connected graph G of order n with minimum degree two different from C 5 and C 7 , satisfies γ dR (G) ≤ 11 10 n. In this paper, we show that this upper bound can be improved to 20 19 n if G is restricted to connected graphs of order n with minimum degree at least two and no C 5 -cycle such that G ∉ { C 7 , C 11 , C 13 , C 17 }. Moreover, we provide an infinite family of graphs attaining this bound.
- Subjects
CHARTS, diagrams, etc.; DOMINATING set; GRAPH connectivity; MAXIMA &; minima
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 2, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-021-02434-2