We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Disprove of a conjecture on the double Roman domination number.
- Authors
Shao, Z.; Khoeilar, R.; Karami, H.; Chellali, M.; Sheikholeslami, S. M.
- 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. Khoeilar et al. (Discrete Appl. Math. 270:159–167, 2019) proved that if G is a connected graph of order n with minimum degree two different from C 5 and C 7 , then γ dR (G) ≤ 11 10 n. Moreover, they presented an infinite family of graphs G attaining the upper bound, and conjectured that G is the only family of extremal graphs reaching the bound. In this paper, we disprove this conjecture by characterizing all extremal graphs for this bound.
- Subjects
DOMINATING set; LOGICAL prediction; GRAPH connectivity
- Publication
Aequationes Mathematicae, 2024, Vol 98, Issue 1, p241
- ISSN
0001-9054
- Publication type
Article
- DOI
10.1007/s00010-023-01029-x