Quaestiones Mathematicae · 2018 · 12 citations · 9 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryTheory Of ComputationDirected Acyclic GraphsDominance HierarchiesGraph TheoryBounding FunctionsDominance Analysis
An Italian dominating function (IDF) on a graph G = (V, E) is a function f: V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V (G) with f (v) = 0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1. The weight of an IDF f is the value ∑v∈V(G) f (v). The Italian domination number of a graph G, denoted by γI (G), is the minimum weight of an IDF on G. An IDF f on G is called a global Italian dominating function (GIDF) on G if f is also an IDF on the complement Ḡ of G. The global Italian domination number of G, denoted by γgI (G), is the minimum weight of a GIDF on G. In this paper, we initiate the study of the global Italian domination number and we present some strict bounds for the global Italian domination number. In particular, we prove that for any tree T of order n ≥ 4, γgI (T) ≤ γI (T) + 2 and we characterize all trees with γgI (T) = γI (T) + 2 and γgI (T) = γI (T) + 1.
9
Michael A. Henning, William F. Klostermeyer · Discrete Applied Mathematics · 2016 · 97 citations
The global domination number of a graph
E. Sampathkumar · 1989 · 77 citations
Robert C. Brigham, Ronald D. Dutton · Discrete Mathematics · 1990 · 43 citations · Full text
Global Roman domination in graphs
P. Roushini Leely Pushpam, S. Padmapriea · Discrete Applied Mathematics · 2015 · 22 citations
On Roman, Global and Restrained Domination in Graphs
Vadim Zverovich, Anush Poghosyan · Graphs and Combinatorics · 2010 · 21 citations · Full text