1. Introduction

By a graph G = (V, E), we mean a finite undirected connected graph without loops or multiple edges. The order and size of G are denoted by p and q respectively. For basic graph theoretic terminology we refer to [2, 4, 5]. The neighborhood of a vertex v is the set N(v) consisting of all vertices u which are adjacent with v. The closed neighborhood of a vertex v is the set N[v] = N(v) ⋃{v}. A vertex v is an extreme vertex if the subgraph induced by its neighbors is complete. A vertex v is a semi-extreme vertex of G if the subgraph induced by its neighbors has a full degree vertex in N(v). In particular, every extreme vertex is a semi-extreme vertex and a semi-extreme vertex need not be an extreme vertex.

A chord of a path u₁, u₂,…,u_k in G is an edge u_iu_j with j ≥ i + 2. A u – v path P is called a monophonic path if it is a chordless path. A set M of vertices is a monophonic set if every vertex of G lies on a monophonic path joining some pair of vertices in M, and the minimum cardinality of a monophonic set is the monophonic number m(G). A monophonic set of cardinality m(G) is called an m-set of G. The monophonic number of a graph G was studied in [3]. A

dominating set in a graph G is a subset of vertices of G such that every vertex outside the subset has a neighbor in it. The size of a minimum dominating set in a graph G is called the domination number of G and is denoted [6].

A set of vertices of G is said to be monophonic domination set if it is both monophonic set and a dominating set of G. The minimum cardinality among all the monophonic dominating sets of G is called a monophonic domination number and is denoted by [8]. The restrained edge monophonic number of a graph was studied in [9].

Theorem 1.1 [10] Each extreme vertex of a connected graph G belongs to every monophonic set of G.

Throughout this paper G denotes a connected graph with at least two vertices.

2. Restrained Monophonic Domination Number

Definition 2.1 A set M of vertices of a connected graph G is a restrained monophonic domination set if either V= M or M is a monophonic dominating set with the subgraph G[V – M] induced by V – M has no isolated vertices. The minimum cardinality of a restrained monophonic dominating set of G is the restrained monophonic domination number of G, and is denoted by

Example 2.2 For the graph G given in Figure 1, M ₁ = {v₁ , v₄ } is a monophonic set of G and so m(G) = 2; M₂ = {v₁ , v_{4 ,} v₁₀} is a monophonic dominating set of G and so M₃ = {v₁ , v_{4 ,}v_10,v₁₁} is a restrained monophonic dominating set of G and so

Figure 1. A graph G for restrained monophonic domination numbers

Theorem 2.3 Each semi-extreme vertex of a graph G belongs to every restrained monophonic dominating set of G. In particular, if the set M of all semi-extreme vertices of G is a restrained monophonic dominating set, then M is the unique minimum restrained monophonic dominating set of G.

Proof. Let M be the set of all semi-extreme vertices of G, and let N be any restrained monophonic dominating set of G. Suppose that there exists a vertex u ∈ M such that u ∉ N. Since there exists v ∈ N(u) such that Since N is a restrained monophonic dominating set of G, the edge e = u v lies on a x - y monophonic path P : x = x₀, x₁,….,x_i-1, x_i = u, x_i+1 = v,…,x _n = y with x, y ∈ N. Since u ∉ N, it is clear that u is an internal vertex of a path P. Since we see that v is adjacent to x_i-1, which is a contradiction to the fact that P is a x – y monophonic path. Hence M is contained in every restrained monophonic dominating set of G.

Theorem 2.4 For any connected graph G,

Proof. A monophonic set needs at least two vertices and therefore m(G) ≥ 2. Also every monophonic dominating set is a monophonic set of G, and then or p – 1, then m_r(G) = p the converse need not be true. Also since every restrained monophonic dominating set of G is an monophonic dominating set of G, and then The complement of each restrained monophonic dominating set has cardinality different from 1 we have Thus there is no graph G of order p with Hence

Theorem 2.5 If a graph G of order p has exactly one vertex of degree p – 1, then

Proof. Let G be a Graph of order p with exactly one vertex of degree p – 1, and let it be u. Since the vertex u is adjacent to all other vertices in G, then any vertex v where v ∈V(G) - {u}, is not an internal vertex of any monophonic path joining two vertices of G other than u and v. Hence

Corollary 2.6 For the complete graph K_p( p ≥ 2),

Proof. Since every vertex of the complete graph K_p (p ≥ 2) is a extreme vertex, by Theorem 2.3, the vertex set of K_p is the minimum restrained monophonic dominating set of K_p. Thus

Theorem 2.7 For the complete bipartite graph G = K_m,n , if 3 ≤ m ≤ n.

Proof. Let X and Y be the partite sets with |X| = m, |Y| = n. If 3 ≤ m ≤ n, then any minimum restrained monophonic dominating set of G is got by choosing two elements from X and Y so that

3. Realization Result

Theorem 3.1 For any integers a, b, c with 3 ≤ a ≤ b < c, then there exists a connected graph G such that m(G) = a,

Proof. Case 1 3 ≤ a = b < c

Let P : x, y, z be a path of order 3. We first add a – 1 new vertices u₁, u₂,....,u_a-1 to P and join these to x. We then add c – a new vertices w₁,w₂,…,w_c-a and join these to both x and z, there by producing the graph G given in Figure 2.

Figure 2. The graph G in Case 1 of Theorem 3.1

First we show that m(G) = a. Since each u_i (1≤ i ≤ a-1) is a extreme vertex of G, by Theorem1.1, each u_i (1≤ i ≤ a-1) belongs to every monophonic set of G. Let M = {u₁, u_2,..., u_a-1}. Then M is not a monophonic set of G and so m(G) ≥ a . However, M₁=M ⋃ { z } is a monophonic set of G, and so m(G) = a. Clearly Next, we show that M₂ = M ⋃{w₁, w₂, …, w_c-a} is a minimum restrained monophonic dominating set of G, so that

Case 2 a + 1 = b < c

Let C₆ : v₁, v₂, v₃, v₄, v₅, v₆ be a cycle of order 6, and let P₃: x, y ,z be a path of order 3. Let H be a graph obtained from C₆ and P₃ by identifying the vertex v₁ in C₆ and the vertex z in P₃. We first add a – 1 new vertices u₁, u₂,...,u_a-1 to H, and join these to x. We then add c – b new vertices w₁,w₂,...., w_c-b and join these to both v₂ and v₄, there by producing the graph G given in Figure 3.

Figure 3. The graph G in Case 2 of Theorem 3.1

First we show that m(G) = a. Since each u_i (1≤ i ≤ a-1) is a extreme vertices of G, by Theorem 1.1, each u_i (1≤ i ≤ a-1) belongs to every monophonic set of G. Let M = {u₁, u_2,...,u_a-1}. M is not a monophonic set of G, and so m(G)≥a. However, M₁=M ⋃ {v₄} is a monophonic set of G, and so m(G) = a. Next, we show that Let M₂ = M₁ ⋃ {v₁} is a monophonic dominating set of G, and so It is clear that M₃ = M ⋃ { w₁, w_2,....,w_c-b} is a minimum restrained monophonic dominating set of G, so that

Case 3 a + 2 ≤ b < c

Let C₄ :v₁, v₂, v₃, v₄ be a cycle of order 4, and let P : u_1,u_2,....,u_3(b-a) be a path of order 3(b – a). Let H be a graph obtained from C₄ and P by identifying the vertex v₄ in C₄ and u₁ in P, and then joining v₄ and u₁. We first add a – 1 new vertices z₁, z₂,....z_a-1 to H and join these to v₁. We then add c – b new vertices w₁,w₂,....,w_c-b and join these to both v₁ and v₄, there by producing the graph G given in Figure 4.

Figure 4. The graph G in Case 3 of Theorem 3.1

First we show that m(G) = a. Since each u_i (1≤ i ≤ a-1) is a extreme vertices of G, by Theorem 1.1, each u_i (1≤ i ≤ a-1) belongs to every monophonic set of G. Let M = {z₁, z_2, ..., z_a-1}. M is not a monophonic set of G, and so m(G)≥a. However, M₁=M ⋃ {u_3(b-a)} is a monophonic set of G, and so m(G) = a. Next, we show that It is clear that M₁ is not a monophonic dominating set of G. Clearly M₂ = M₁ ⋃ { v_4, u_2, u_5, ...., u_3(b-a)} is a monophonic dominating set of G, and so Next, we show that It is clear that M₃ = M₂ ⋃ {w_1,w_2,....,w_c-b} is a minimum restrained monophonic dominating set of G, and so that

4. Conclusions

In this paper the authors introduced the restrained monophonic domination number and the restrained monophonic domination number of some connected graph are realized. The authors obtained the restrained edge monophonic domination number, connected restrained monophonic domination number, and forcing restrained monophonic domination number in the subsequent papers. It has so many application in security of buildings and communication networks.

ACKNOWLEDGEMENTS

The authors are grateful to the anonymous referee for a careful checking of the details and for helpful comments that improved this paper.