Secure Italian domination in graphs
- PDF / 417,061 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 58 Downloads / 213 Views
Secure Italian domination in graphs M. Dettlaff1
1 · J. A. Rodríguez-Velázquez2 · M. Lemanska ´
Accepted: 29 September 2020 © The Author(s) 2020
Abstract An Italian dominating function (IDF) on a graph G is a function f : V (G) → {0, 1, 2} such that for every vertex v with f (v) = 0, the total weight of f assigned to the neighbours of v is at least two, i.e., u∈NG (v) f (u) ≥ 2. For any function f : V (G) → {0, 1, 2} and any pair of adjacent vertices with f (v) = 0 and u with f (u) > 0, the function f u→v is defined by f u→v (v) = 1, f u→v (u) = f (u) − 1 and f u→v (x) = f (x) whenever x ∈ V (G)\{u, v}. A secure Italian dominating function on a graph G is defined as an IDF f which satisfies that for every vertex v with f (v) = 0, there exists a neighbour u with f (u) > 0 such that f u→v is an IDF. The weight of f is ω( f ) = v∈V (G) f (v). The minimum weight among all secure Italian dominating functions on G is the secure Italian domination number of G. This paper is devoted to initiating the study of the secure Italian domination number of a graph. In particular, we prove that the problem of finding this parameter is NP-hard and we obtain general bounds on it. Moreover, for certain classes of graphs, we obtain closed formulas for this novel parameter. Keywords Domination number · Secure domination number · Italian domination · Secure Italian domination Mathematics Subject Classification 05C69
B
M. Dettlaff [email protected] M. Lema´nska [email protected] J. A. Rodríguez-Velázquez [email protected]
1
Department of Technical Physics and Applied Mathematics, Gdansk University of Technology, ul. Narutowicza 11/12, 80-233 Gda´nsk, Poland
2
Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain
123
Journal of Combinatorial Optimization
1 Introduction The following approach to protection of a graph was described by Cockayne et al. (2005). Suppose that one or more guards are stationed at some of the vertices of a simple graph G and that a guard at a vertex can deal with a problem at any vertex in its closed neighbourhood. Consider a function f : V (G) −→ {0, 1, 2} where f (v) is the number of guards at v, and let Vi = {v ∈ V (G) : f (v) = i} for every i ∈ {0, 1, 2}. We will identify a function f with the subsets V0 , V1 , V2 of V (G) associated with it, and so we will use the unified notation f (V0 , V1 , V2 ) for the function and these associated subsets. The weight of f is defined to be ω( f ) = f (V (G)) = |V1 |+2|V2 |. Informally, we say that G is protected under f if there is at least one guard available to handle a problem at any vertex. Next we show some approaches to the protection of graphs. The functions in each approach protect the graph according to a certain strategy. We assume that the reader is familiar with the basic concepts, notation and terminology of domination in graphs. If this is not the case, we suggest the textbooks (Haynes et al. 1998a, b). For the remainder of the paper, defi
Data Loading...
