On double Roman domination problem for several graph classes

DOI10.1007/S00010-024-01071-3MaRDI QIDQ6991584zbMATH OpenFDO

Authors Dragan Matić, Marko Djukanovic

Publication date 28 April 2025

Published in Aequationes Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00010-024-01071-3

zbMATH Keywords

convex polytopesdouble Roman dominationflower snarksgeneralized Petersen graphsJohnson graphsKneser graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory (05C90) Combinatorics in computer science (68R05)

Review text

Several variants of Roman domination function, such as the signed Roman domination problem, the double Roman domination problem, the signed double Roman domination problem, the triple Roman domination problem, and the perfect Roman domination problem have been extensively studied. These problems deal with different types of defense strategies. This paper deals with the double Roman domination number of a graph. The exact values of this parameter for Kneser graphs \(K_{n,k}\) where \(n\geq k (k+2),\) Johnson graphs \(J_{n,2},\) a few classes of convex polytopes and flower snakes are determined. Tight upper and lower bounds and an improvement of the known upper bound for the generalized Petersen graph \(P_{n,k}(n\not\equiv 0\pmod 4\) are presented. The investigation of other variants of double Roman domination for these graph classes is open.

Cites work

• A theorem on tait colorings with an application to the generalized Petersen graphs
• An improved upper bound on the double Roman domination number of graphs with minimum degree at least two
• An introduction to the discharging method via graph coloring
• An upper bound on the double Roman domination number
• Bounds on the 2-domination number
• Domination number of graphs with minimum degree five
• Double Roman domination
• Double Roman domination and domatic numbers of graphs
• Double Roman domination in graphs with minimum degree at least two and no \(C_5\)-cycle
• scientific article; zbMATH DE number 4081585 (Why is no real title available?)
• scientific article; zbMATH DE number 125446 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Integer linear programming formulations for double Roman domination problem
• On classes of regular graphs with constant metric dimension
• Outer independent double Roman domination
• Perfect double Roman domination of trees
• Perfect Roman domination in trees
• Power domination on triangular grids with triangular and hexagonal shape
• Roman domination in graphs.
• Self-dual configurations and regular graphs
• Several Roman domination graph invariants on Kneser graphs
• Signed double Roman domination in graphs
• Signed Roman \(k\)-domination in graphs
• Signed Roman domination in graphs
• Snarks and reducibility
• The double Roman domination numbers of generalized Petersen graphs \(P(n, 2)\)
• The Philosophical Implications of the Four-Color Problem
• Triple Roman domination in graphs
• Über den kartographischen Vierfarbensatz.

This page was built for publication: On double Roman domination problem for several graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6991584)