On double roman domination edge critical graphs
A double Roman dominating function (or just DRDF) on a graph [Formula: see text] is a function [Formula: see text] having the property that if [Formula: see text] for a vertex [Formula: see text], then [Formula: see text] has at least two neighbors assigned [Formula: see text] or one neighbor assigned [Formula: see text] under [Formula: see text], and if [Formula: see text], then [Formula: see text] has at least one neighbor assigned at least two under [Formula: see text]. The weight of a DRDF [Formula: see text] is the sum [Formula: see text], and the minimum weight of a DRDF on [Formula: see text] is the double Roman domination number of [Formula: see text]. A graph [Formula: see text] is double Roman domination edge critical if the addition of any edge decreases the double Roman domination number, and it is strong double Roman domination edge critical if the addition of any edge decreases the double Roman domination number by two. In this paper, we first answer an open problem posed in [Discrete Math. Alg. Appl. 12 (2020) 2050020] by characterizing all double Roman domination edge critical trees. We then prove some fundamental properties of strong double Roman domination edge critical graphs, and characterize classes of strong double Roman domination edge critical graphs including unicyclic graphs as well as graphs with double Roman domination number at most seven.
Authors
- Nader Jafari Rad (ORCID: https://orcid.org/0000-0001-7406-1859)
- Farshad Sajedi
Institutions
- Shahed University (IR)
Publication Details
- Journal
- Discrete Mathematics Algorithms and Applications
- Published
- 2025-08-26
- DOI
- https://doi.org/10.1142/s1793830925501265
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00