Edge lifting and Roman domination in graphs

被引：0

作者：

Meraimi, Hicham ^{[1
]}

Chellali, Mustapha ^{[2
]}

机构：

[1] Univ Sci & Technol Houari Boumediene USTHB, Fac Math, Lab LIFORCE, Algiers, Algeria

[2] Univ Blida, Dept Math, LAMDA RO Lab, BP 270, Blida, Algeria

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2021年 / 13卷 / 05期

关键词：

Edge splitting; edge lifting; Roman domination;

D O I：

10.1142/S1793830921500646

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be a graph, and let uxv be an induced path centered at x. An edge lift defined on uxv is the action of removing edges ux and vx while adding the edge uv to the edge set of G. In this paper, we initiate the study of the effects of edge lifting on the Roman domination number of a graph, where various properties are established. A characterization of all trees for which every edge lift increases the Roman domination number is provided. Moreover, we characterize the edge lift of a graph decreasing the Roman domination number, and we show that there are no graphs with at most one cycle for which every possible edge lift can have this property.

引用

页数：13

共 50 条

[31] Mixed double Roman domination in graphs [J].

Ahangar, H. Abdollahzadeh ;

Chellali, M. ;

Sheikholeslami, S. M. ;

Valenzuela-Tripodoro, J. C. .

COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024,

[32] Global double Roman domination in graphs [J].

Shao, Zehui ;

Sheikholeslami, S. M. ;

Nazari-Moghaddam, S. ;

Wang, Shaohui .

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2019, 22 (01) :31-44

[33] On the strong Roman domination number of graphs [J].

Alvarez-Ruiz, M. P. ;

Mediavilla-Gradolph, T. ;

Sheikholeslami, S. M. ;

Valenzuela-Tripodoro, J. C. ;

Yero, I. G. .

DISCRETE APPLIED MATHEMATICS, 2017, 231 :44-59

[34] Roman domination on strongly chordal graphs [J].

Chun-Hung Liu ;

Gerard J. Chang .

Journal of Combinatorial Optimization, 2013, 26 :608-619

[35] INDEPENDENT [k]-ROMAN DOMINATION ON GRAPHS [J].

Luiz, Atilio g. ;

Vieira, Francisco anderson silva .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2025,

[36] Perfect Roman domination in middle graphs [J].

Kim, Kijung .

DISCRETE MATHEMATICS LETTERS, 2021, 7 :94-97

[37] On the Roman domination in the lexicographic product of graphs [J].

Sumenjak, Tadeja Kraner ;

Pavlic, Polona ;

Tepeh, Aleksandra .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) :2030-2036

[38] Algorithmic aspects of Roman domination in graphs [J].

Chakradhar Padamutham ;

Venkata Subba Reddy Palagiri .

Journal of Applied Mathematics and Computing, 2020, 64 :89-102

[39] Double Roman domination in some graphs [J].

Meena, J. ;

Mai, T. N. M. Malini ;

Suresh, M. L. ;

Rathour, Laxmi ;

Mishra, Lakshmi Narayan .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025,

[40] On the total Roman domination stability in graphs [J].

Asemian, Ghazale ;

Jafari Rad, Nader ;

Tehranian, Abolfazl ;

Rasouli, Hamid .

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2021, 18 (03) :166-172

← 1 2 3 4 5 →