Roman domination in graphs.
From MaRDI portal
Publication:1427467
DOI10.1016/j.disc.2003.06.004zbMath1036.05034OpenAlexW1984228559MaRDI QIDQ1427467
E. J. Cockayne, Sandra M. Hedetniemi, Paul A. jun. Dreyer, Stephen T. Hedetniemi
Publication date: 14 March 2004
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2003.06.004
Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Roman \(\{2 \}\)-domination ⋮ Improved bounds on the \(k\)-tuple (Roman) domination number of a graph ⋮ A new approach on locally checkable problems ⋮ Global triple Roman dominating function ⋮ Computing Roman domatic number of graphs ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Hardness results of global Roman domination in graphs ⋮ Characterization of trees with Roman bondage number 1 ⋮ Some progress on the double Roman domination in graphs ⋮ Relating the outer-independent total Roman domination number with some classical parameters of graphs ⋮ A note on the bounds of Roman domination numbers ⋮ Roman domination in subgraphs of grids ⋮ The \(\mathbb{N}_k\)-valued Roman domination and its boundaries ⋮ Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \(\{2\}\)-domination number ⋮ The Roman domatic problem in graphs and digraphs: a survey ⋮ Total Roman \(\{2\}\)-dominating functions in graphs ⋮ Total protection of lexicographic product graphs ⋮ A new upper bound for the perfect Italian domination number of a tree ⋮ Double Roman domination in generalized Petersen graphs ⋮ Further progress on the total Roman \(\{2\}\)-domination number of graphs ⋮ Double Roman domination ⋮ A note on Roman domination in graphs ⋮ Extremal problems on weak Roman domination number ⋮ Bounds on the double Italian domination number of a graph ⋮ Perfect Italian domination in graphs: complexity and algorithms ⋮ The roman \(k\)-domatic number of a graph ⋮ On the outer independent double Roman domination number ⋮ Coloring, location and domination of corona graphs ⋮ Extremal graphs for a bound on the Roman domination number ⋮ Roman domination on strongly chordal graphs ⋮ Distance restricted optimal pebbling in cycles ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Mixed Roman domination in graphs ⋮ Independent protection in graphs ⋮ Roman \(\{ 3 \}\)-domination (double Italian domination) ⋮ Bounds on the locating Roman domination number in trees ⋮ Perfect Roman domination in trees ⋮ Independent Roman \(\{2 \}\)-domination in graphs ⋮ On the independent double Roman domination in graphs ⋮ On the \(k\)-strong Roman domination problem ⋮ A characterization of perfect Roman trees ⋮ On algorithmic complexity of double Roman domination ⋮ Perfect Italian domination on planar and regular graphs ⋮ On the independent domination number of the generalized Petersen graphs ⋮ Weak \(\{2\}\)-domination number of Cartesian products of cycles ⋮ Nordhaus-Gaddum bounds for total Roman domination ⋮ Defending the Roman Empire from multiple attacks ⋮ Global Roman domination in graphs ⋮ On the roman domination in the lexicographic product of graphs ⋮ Some improved inequalities related to Vizing's conjecture ⋮ On the global Roman domination number in graphs ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Graphs with large Italian domination number ⋮ A constructive characterization of vertex cover Roman trees ⋮ On the co-Roman domination in graphs ⋮ On the total Roman domination in trees ⋮ On the Roman bondage number of planar graphs ⋮ On roman, global and restrained domination in graphs ⋮ \(k\)-domination and \(k\)-independence in graphs: A survey ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ Signed double Roman domination in graphs ⋮ Italian domination in rooted product graphs ⋮ The Roman \(\{2 \}\)-domatic number of graphs ⋮ A characterization of double Roman trees ⋮ Covering Italian domination in graphs ⋮ Perfect Italian domination in trees ⋮ Restricted optimal pebbling and domination in graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Italian domination in trees ⋮ A proof of a conjecture on the differential of a subcubic graph ⋮ Note on 2-rainbow domination and Roman domination in graphs ⋮ Some progress on the restrained Roman domination ⋮ Distance restricted optimal pebbling in paths ⋮ Italian domination in the Cartesian product of paths ⋮ Secure Italian domination in graphs ⋮ The roman domatic number of a graph ⋮ Italian domination of Cartesian products of directed cycles ⋮ Efficient algorithms for Roman domination on some classes of graphs ⋮ On the 2-packing differential of a graph ⋮ A continuous generalization of domination-like invariants ⋮ Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs ⋮ Bounds on weak Roman and 2-rainbow domination numbers ⋮ Algorithmic aspects of Roman domination in graphs ⋮ Defending the Roman Empire---a new strategy ⋮ Roman domination in regular graphs ⋮ Protection of lexicographic product graphs ⋮ On the Roman domination number of a graph ⋮ The secure domination number of Cartesian products of small graphs with paths and cycles ⋮ Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number ⋮ Upper bounds on Roman domination numbers of graphs ⋮ Perfect double Roman domination of trees ⋮ Constructive characterizations concerning weak Roman domination in trees ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set ⋮ Restrained Roman and restrained Italian domatic numbers of graphs ⋮ Computing strong Roman domination of trees and unicyclic graphs in linear time ⋮ On the Roman domination subdivision number of a graph ⋮ Secure domination critical graphs ⋮ Restrained condition on double Roman dominating functions ⋮ Further results on packing related parameters in graphs ⋮ Roman \(\{2\}\)-domination problem in graphs ⋮ A note on the Roman domatic number of a digraph ⋮ Unnamed Item ⋮ Resolving Roman domination in graphs ⋮ A characterization of trees with equal Roman $\{2\}$-domination and Roman domination numbers ⋮ Weak Roman subdivision number of graphs ⋮ On trees with equal Roman domination and outer-independent Roman domination numbers ⋮ On Hop Roman Domination in Trees ⋮ Unnamed Item ⋮ On the perfect differential of a graph ⋮ Unitary Cayley graphs whose Roman domination numbers are at most four ⋮ Trees with total Roman domination number equal to Roman domination number plus its domination number: complexity and structural properties ⋮ Perfect Domination, Roman Domination and Perfect Roman Domination in Lexicographic Product Graphs ⋮ ON THE CHARACTERIZATION OF ROMAN DOMINATING SETS IN TREES ⋮ Protection of graphs with emphasis on Cartesian product graphs ⋮ Roman domination and 2-independence in trees ⋮ Secure vertex cover of a graph ⋮ Further results on the independent Roman domination number of graphs ⋮ On the outer independent total double Roman domination in graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Triple Roman domination subdivision number in graphs ⋮ Algorithmic aspects of outer independent Roman domination in graphs ⋮ Graphs whose weak Roman domination number increases by the deletion of any edge ⋮ Total Italian domatic number of graphs ⋮ Unnamed Item ⋮ Unique response Roman domination: complexity and algorithms ⋮ Approximation algorithm for (connected) Italian dominating function ⋮ Roman \(k\)-domination: hardness, approximation and parameterized results ⋮ Quasi-total Roman bondage number in graphs ⋮ Further results on independent double roman trees ⋮ Order-sensitive domination in partially ordered sets and graphs ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Quasi-total Roman reinforcement in graphs ⋮ Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs ⋮ The Outer-Paired Domination of Graphs ⋮ On the double Roman bondage numbers of graphs ⋮ Incidence‐free sets and edge domination in incidence graphs ⋮ Roman domination and independent Roman domination on graphs with maximum degree three ⋮ Closed formulas for the independent (Roman) domination number of rooted product graphs ⋮ Outer independent double Italian domination: Complexity, characterization ⋮ Complexity aspects of restrained Roman domination in graphs ⋮ Perfect double Italian domination of a graph ⋮ On [ k -Roman domination in graphs] ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ On balanced cycle domination of graphs ⋮ Hop total Roman domination in graphs ⋮ New results on quadruple Roman domination in graphs ⋮ Roman {2}-domination in Graphs and Graph Products ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width ⋮ EDGE ITALIAN DOMINATION OF SOME GRAPH PRODUCTS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness results of global Roman domination in graphs ⋮ An upper bound on the double Roman domination number ⋮ Perfect roman domination in regular graphs ⋮ A Note on Roman $k$-tuple domination number ⋮ Efficient algorithms for independent Roman domination on some classes of graphs ⋮ Regular graphs with large Italian domatic number ⋮ Unnamed Item ⋮ Algorithmic Aspects of Quasi-Total Roman Domination in Graphs ⋮ Independent roman $\{3\}$-domination ⋮ Unnamed Item ⋮ On maximal Roman domination in graphs ⋮ Unnamed Item ⋮ R<scp>OMAN DOMINATION</scp>: a parameterized perspective† ⋮ Domination-related parameters in rooted product graphs ⋮ A Roman domination chain ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Roman k-tuple domination number of a graph ⋮ Trees with equal Roman {2}-domination number and independent Roman {2}-domination number ⋮ A Nordhaus–Gaddum bound for Roman domination ⋮ Domination problems on P5-free graphs ⋮ An algorithm to recognize weak roman domination stable trees under vertex deletion ⋮ On the total Roman domination stability in graphs ⋮ Double Roman reinforcement number in graphs ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Quadruple Roman domination in graphs ⋮ Isolate Roman domination in graphs ⋮ Bounds on signed total double Roman domination ⋮ Outer independent Roman domination number of trees ⋮ Vertex-Edge Roman Domination ⋮ Integer linear programming formulations for double roman domination problem ⋮ Perfect Roman domination in middle graphs ⋮ Unnamed Item ⋮ Roman domination dot-critical graphs ⋮ On the outer-independent double Italian domination number ⋮ Lower and upper bounds on independent double Roman domination in trees ⋮ Outer independent Roman dominating functions in graphs ⋮ Unnamed Item ⋮ Trees with unique Roman dominating functions of minimum weight ⋮ Relations between the Roman k-domination and Roman domination numbers in graphs ⋮ Upper bounds on the \(k\)-tuple (Roman) domination number of a graph ⋮ Vertex-addition strategy for domination-like invariants ⋮ On the strong Roman domination number of graphs ⋮ Triple Roman domination in graphs ⋮ Perfect Italian domination in cographs ⋮ On the total and strong version for Roman dominating functions in graphs ⋮ Independent Roman domination and 2-independence in trees ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ On the Roman domination stable graphs ⋮ On the double Roman domination in graphs ⋮ On the differential and Roman domination number of a graph with minimum degree two ⋮ On the signed Roman \(k\)-domination: complexity and thin torus graphs ⋮ Structure of wheel-trees with colourings and domination numbers ⋮ Roman domination in direct product graphs and rooted product graphs ⋮ Exact algorithms for weak Roman domination ⋮ Total Roman domination in the lexicographic product of graphs ⋮ On the weak Roman domination number of lexicographic product graphs ⋮ Roman edge semi-total block domination of a graph ⋮ Tight bounds for eternal dominating sets in graphs ⋮ Trees with equal strong Roman domination number and Roman domination number ⋮ Graphs with small Italian domatic number ⋮ Independent double Roman domination in graphs ⋮ Signed Roman domination in graphs ⋮ A note on the double Roman domination number of graphs ⋮ Roman dominating influence parameters ⋮ Unnamed Item ⋮ From the strong differential to Italian domination in graphs ⋮ Roman domination and double Roman domination numbers of Sierpiński graphs \(S(K_n,t)\) ⋮ ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS ⋮ Maximal double Roman domination in graphs ⋮ ON THE ROMAN BONDAGE NUMBER OF A GRAPH ⋮ Mixed Roman domination and 2-independence in trees ⋮ Quasi-total Roman domination in graphs ⋮ Unique response Roman domination in graphs ⋮ Trees with independent Roman domination number twice the independent domination number ⋮ Roman \(\{2\}\)-bondage number of a graph ⋮ Note on the perfect Roman domination number of graphs ⋮ Critical graphs with Roman domination number four ⋮ Varieties of Roman domination II ⋮ Complexity of Roman {2}-domination and the double Roman domination in graphs ⋮ The geodetic domination number of comb product graphs ⋮ Algorithmic results on double Roman domination in graphs ⋮ Approximation algorithm for a generalized Roman domination problem in unit ball graphs ⋮ Effect of vertex deletion on the weak Roman domination number of a graph ⋮ Unnamed Item ⋮ The signed Roman domination number of two classes graphs ⋮ The Private Neighbor Concept ⋮ Varieties of Roman Domination ⋮ Roman Domination in Graphs ⋮ Rainbow Domination in Graphs ⋮ Eternal and Secure Domination in Graphs ⋮ Global Domination ⋮ Independent double Roman domination in graphs ⋮ Algorithmic and complexity aspects of problems related to total Roman domination for graphs ⋮ The Roman domination number of some special classes of graphs - convex polytopes ⋮ Double Roman domination and domatic numbers of graphs ⋮ Total Roman reinforcement in graphs ⋮ Roman domination excellent graphs: trees ⋮ On the domination number of some graphs ⋮ Total Roman domatic number of a graph ⋮ Bounds on the co-Roman domination number in graphs ⋮ Roman domination in unicyclic graphs ⋮ Total Roman domination in digraphs ⋮ Weakly connected Roman domination in graphs ⋮ Properties of double Roman domination on cardinal products of graphs ⋮ Unnamed Item ⋮ On roman domination number of functigraph and its complement ⋮ Outer-independent total Roman domination in graphs ⋮ Extremal digraphs for an upper bound on the Roman domination number ⋮ On Clark and Suen bound-type results fork-domination and Roman domination of Cartesian product graphs ⋮ Perfect Roman domination in graphs ⋮ Remarks on the outer-independent double Italian domination number ⋮ On the double Roman domination of graphs ⋮ A note on the edge Roman domination in trees ⋮ On the complexity of some hop domination parameters ⋮ On trees with domination number equal to edge-vertex roman domination number ⋮ Co-Roman domination in graphs ⋮ Trees with vertex-edge roman domination number twice the domination number minus one ⋮ On the roman domination number of generalized Sierpiński graphs ⋮ LIMITED DOMINATING BROADCAST IN GRAPHS ⋮ On the Roman {2}-domatic number of graphs ⋮ Algorithmic aspects of total Roman {3}-domination in graphs ⋮ Edge lifting and Roman domination in graphs ⋮ ALGORITHMIC ASPECTS OF ROMAN GRAPHS ⋮ Global Roman domination in trees ⋮ Total Roman domination subdivision number in graphs ⋮ Global double Roman domination in graphs
Cites Work
This page was built for publication: Roman domination in graphs.
