On the Mixed Minus Domination in Graphs
- PDF / 317,490 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 241 Views
On the Mixed Minus Domination in Graphs Baogen Xu · Xiangyang Kong
Received: 6 April 2013 / Revised: 20 August 2013 / Accepted: 21 August 2013 / Published online: 12 September 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
Abstract Let G = (V , E) be a graph, for an element x ∈ V ∪ E, the open total neighborhood of x is denoted by Nt (x) = {y|y is adjacent to x or y is incident with x, y ∈ V ∪ E}, and Nt [x] = Nt (x) ∪ {x} is the closed one. A function f : V (G) ∪ E(G) → {−1, 0, 1} is said to be a mixed minus domination function (TMDF) of G if y∈Nt [x] f (y) 1 holds for all x ∈ V (G) ∪ E(G). The mixed minus domination (G) of G is defined as number γtm (G) = min f (x)|f is a TMDF of G . γtm x∈V ∪E
In this paper, we obtain some lower bounds of the mixed minus domination num (G) when G is a cycle or a path. ber of G and give the exact values of γtm Keywords Mixed minus domination function · Mixed minus domination number
1 Introduction We use Bondy and Murty [1] for terminology and notation not defined here and consider finite connected simple graphs only. Let G be a graph with the vertex set V (G) and edge set E(G). The neighborhood of vertex v is the set {u|uv ∈ E(G)}, which is denoted by N (v), and N [v] = N(v) ∪ {v} is the closed neighborhood of v. A function f : V (G) → {−1, 0, 1} is called a minus domination function (shortly MDF) of G, if f [v] = f (N[v]) = This work was supported by the National Natural Science Foundation of China (No. 11061014, 11361024, 11261019) and the Science Foundation of Jiangxi Province (No. KJLD12067).
B
B. Xu ( ) · X. Kong Department of Mathematics, East China Jiaotong University, Nanchang, Jiangxi 330013, China e-mail: [email protected]
386
B. Xu, X. Kong
u∈N [v] f (u) 1 for each v ∈ V (G). It was introduced by J.E. Dunbar et al. in [2], and has been studied by other authors in [3–5]. Quite analogously, the neighborhood of edge e is a set {e |e ∈ E(G) and e is adjacent to e}, which is denoted by N (e), and N[e] = N (e) ∪ {e} is the closed edge neighborhood of e. We call a function f : E(G) → {−1, 0, 1} a minus edge domination function (shortly MEDF) of G, if f [e] = f (N[e]) = e ∈N [e] f (e ) 1 for each e ∈ E(G). The weight ω(f ) of f is the sum of the function values of all edges in G. The minus edge domination number γm (G) of G is the minimum weight of a minus edge domination function on G, see [6]. In this paper, for an element x ∈ V (G) ∪ E(G), the open total neighborhood of x is denoted by Nt (x) = {y|y is adjacent to x or y is incident with x, y ∈ V (G) ∪ E(G)}, and the closed total neighborhood of x is denoted by Nt [x] = Nt (x) ∪ {x}.
Definition 1.1 Let G be a finite connected simple graph. A function f : V (G) ∪ E(G) → {−1, 0, 1} is called a mixed minus domination function (TMDF) of G if y∈Nt [x] f (y) 1 holds for each x ∈ V (G) ∪ E(G). The mixed minus domination (G) of G is defined as number γtm γtm (G) = min f (x)|f is a TMDF of G . x∈V (G
Data Loading...
