Graphs with Large Italian Domination Number
- PDF / 390,790 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 250 Views
Graphs with Large Italian Domination Number Teresa W. Haynes1,2 · Michael A. Henning2 · Lutz Volkmann3 Received: 11 June 2019 / Revised: 21 February 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract An Italian dominating function on a graph G with vertex set V (G) is a function f : V (G) → {0, 1, 2} having the property that for every vertex v with f (v) = 0, at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f . The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f . The Italian domination number of G, denoted by γ I (G), is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order n ≥ 3, then γ I (G) ≤ 43 n. Further, if G has minimum degree at least 2, then γ I (G) ≤ 23 n. In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus– Gaddum inequalities for the Italian domination number. Keywords Domination · Italian domination · Roman domination · Roman {2}-domination AMS subject classification: 05C69
Communicated by Xueliang Li.
B
Teresa W. Haynes [email protected] Michael A. Henning [email protected] Lutz Volkmann [email protected]
1
Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-0002, USA
2
Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park 2006, South Africa
3
Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany
123
T. W. Haynes et al.
1 Introduction Cockayne et al. [3] first introduced Roman domination as a graphical invariant in 2004, following a series of papers (see [13–16]) on defense strategies of the ancient Roman Empire. Since its introduction, over 100 papers have been published on Roman domination and its variants. We refer the reader to [1,7,9,10] for some recent papers on Roman domination. In this paper, we consider Italian domination, a variant of Roman domination. Italian domination was introduced as Roman {2}-domination in [2] and was renamed and studied further in [5]. See also [8,12]. Let G be a graph with vertex set V (G) and edge set E(G). Two vertices v and w are neighbors in G if they are adjacent; that is, if vw ∈ E(G). The open neighborhood of a vertex v in G is the set of neighbors of v, denoted by N G (v), and its closed neighborhood is N G [v] = N G (v) ∪ {v}. A function f : V (G) → {0, 1, 2} is a Roman dominating function, abbreviated RD-function, on G if every vertex u ∈ V (G) for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a RD-function is the value w( f ) = f (V (G)) = u∈V (G) f (u). The Roman domination number γ R (G) is the minimum weight of a RD-function on G, and a RD-function with weight γ R (G) is called a γ R -function of G. One may view Roman domination as graph labeling problem in which each vertex labeled 0 must be adjacent to at least on
Data Loading...
