Further results on the signed Italian domination
- PDF / 423,833 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 199 Views
Further results on the signed Italian domination A. Karamzadeh1 · H. R. Maimani1
· A. Zaeembashi1
Received: 28 July 2020 / Revised: 5 November 2020 / Accepted: 10 November 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract A signed Italian dominating function on a graph G = (V , E) is a function f : V → {−1, 1, 2} satisfying the condition that for every vertex u, f [u] ≥ 1. The weight of the signed Italian dominating function, f , is the value f (V ) = u∈V f (u). The signed Italian dominating number of a graph G, denoted by γs I (G), is the minimum weight of a signed Italian dominating function on a graph G. In this paper, we prove that for and we characterize all trees attaining this any tree T of order n ≥ 2, γs I (T ) ≥ −n+4 2 bound. In addition, we obtain some results about the signed Italian domination number of some graph operations. Furthermore, we prove that the signed Italian domination problem is NP-Complete for bipartite graphs. Keywords Domination · Signed Italian dominating function · Signed Italian dominating number Mathematics Subject Classification 05C69
1 Introduction In this paper, G is a simple graph with the vertex set V = V (G) and the edge set E = E(G). The order |V | of G is denoted by n. For every vertex v ∈ V , the open neighborhood N (v) is the set {u ∈ V (G) | uv ∈ E(G)} and the closed neighborhood of v is the set N [v] = N (v) ∪ {v}. For every vertex v ∈ V the number of neighbors of v is denoted by degG (v). We denote degG (v) by dG (v)
B
H. R. Maimani [email protected] A. Karamzadeh [email protected] A. Zaeembashi [email protected]
1
Mathematics Section, Department of Basic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran
123
A. Karamzadeh et al.
for notational convenience. The minimum and maximum degree of a graph G are denoted by δ and , respectively. A signed dominating function (SDF) on a graph G = (V , E) is a function f : V → {−1, 1} such that f [v] ≥ 1 for every vertex v ∈ V . The signed domination number, denoted by γs (G), is the minimum weight of a SDF in G; that is, γs (G) = min{w( f ) | f is a SDF in G}. An Italian dominating function (IDF) or a Roman {2}-dominating function on a graph G = (V , E) is a function f : V → {0, 1, 2} with the property that for every vertex v ∈ V 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 under f . The Italian domination function number γ I (G) equals to the minimum weight of an Italian dominating function on G. An Italian domination has been introduced in 2015 by Chellali et al. [1], and studied further in [4,5]. In this paper, we continue the study of the signed Italian domination in graphs introduced in [6] as follows. A signed Italian dominating function (SIDF) on graph G = (V , E) is a function f : V → {−1, 1, 2} which has the property that for every vertex v ∈ V the sum of the values assigned to vertex v and its neighbors is at least 1. Thus a signed Italian dominati
Data Loading...
