The connected monophonic eccentric domination number of a graph

1 Introduction

We refer to a graph G = (V, E) as a non-trivial simple connected graph with |V (G) | = p and |E (G) | = q. The order and size of G are denoted by p and q, respectively. We refer to [1, 3] for basic graph theoretic terminology and results. The distance d (u, v) represents the length of a shortest u - v path in G. If d (u, v) is either 0 or 1, then v dominates u (or u dominates v). If S is a set of vertices of G and every vertex of G is dominated by some vertex in S, then S is called a dominating set and the minimum cardinality of S is called the domination number of G. The domination number is denoted by γ (G). Berge [1] and Ore [5] introduced the concept of domination. Then Haynes et al. [4] published a textbook on domination in the year 1998. If S ⊆ V is a dominating set of G and its induced subgraph is connected, then S is called a connected dominating set of G. The connected domination number γ _c  (G) is the minimum cardinality of a connected dominating set of G and it was studied in [6].

The detour distance D (u, v) represents the length of a longest u - v path in G. Define D^- (v) = min {D (u, v) : u ∈ V - {v}} for each vertex v in G. A vertex u  (≠ v) is a detour neighbor of v if D (u, v) = D^- (v). If u = v or u is a detour neighbour of v, then the vertex v is said to detour dominate the vertex u. If S is a set of vertices of G and each vertex of G is detour dominated by some vertex in S, then S is called a detour dominating set of G. The detour domination number γ _D  (G) is the minimum cardinality of a detour dominating set of G. Chartrand et al. [2] introduced and explored these topics.

The distance and detour distance between any two vertices in a connected graph are respectively, based on a shortest path and a longest path between the vertices. In the year 2011, Santhakumaran and Titus [7] introduced a new distance known as monophonic distance based on a chordless path between any two vertices in a connected graph and further it was studied in [8].

A path’s chord is an edge that connects two non-adjacent vertices. If a path P is chordless, it is called a monophonic path. The monophonic distance d _m  (u, v) represents the length of a longest u - v monophonic path in G. The monophonic eccentricity e _m  (v) of a vertex v is defined as e _m  (v) = max {d _m  (u, v) : u ∈ V}. The monophonic radius of G is defined as rad _m  (G) = min {e _m  (v) : v ∈ V}. The monophonic diameter of G is defined as diam _m  (G) = max {e _m  (v) : v ∈ V} . If e _m  (u) = d _m  (u, v), then v is a monophonic eccentric vertex of u in G. If e _m  (v) = rad _m  (G), a vertex v in G is a monophonic central vertex, and the monophonic center of G is the subgraph induced by the monophonic central vertices of G. The graph G is called monophonic self-centered if every vertex of G is a monophonic central vertex.

Let S be a set of vertices of G. If every vertex in V - S has a monophonic eccentric vertex in S, then S is called a monophonic eccentric dominating set or MED-set of G. The monophonic eccentric domination number or MED-number γ _me  (G) is the minimum cardinality of a MED-set of G. Titus et al. [9] introduced and investigated these topics.

In the sequel, the following theorems will be applied.

Theorem 1. [9] If G is a cycle of order p and p ≡ l (mod 6), then γ me ( G ) = { ⌈ p 3 ⌉ + 1 if l = 2 ⌈ p 3 ⌉ otherwise .

Theorem 2. [9] If G is a wheel of order p and p ≡ l (mod 6), then γ me ( G ) = { p 3 + 1 if l = 3 ⌈ p - 1 3 ⌉ otherwise .

2 The CMED-number

Definition 1. Let G = (V, E) be a connected graph with at least two vertices. A set S ⊆ V is a connected monophonic eccentric dominating set or CMED-set if S is a MED-set and the induced subgraph is connected. The connected monophonic eccentric domination number or CMED-number γ _cme  (G) is the cardinality of a minimum CMED-set of G.

Example 1. Consider the graph G given in Fig. 1. The set {v₂, v₆} is the unique minimum MED-set of G so that γ _me  (G) =2. Also, the set {v₁, v₂, v₃} is a minimum CMED-set of G so that γ _cme  (G) =3.

OPEN IN VIEWER

Fig. 1

A graph G with γ _cme  (G) =3.

   Since any CMED-set is necessarily a MED-set, the following theorem is obvious.

Theorem 3. For any connected graph G, γ _me  (G) ≤ γ _cme  (G).

Theorem 4. For any connected graph G of order p ≥ 2, 1 ≤ γ _cme  (G) ≤ p - 1.

Proof. If v is not a cut-vertex of G, then V (G) - {v} is a CMED-set of G and so γ _cme  (G) ≤ p - 1. Also, every CMED-set of G contains at least one vertex and so γ _cme  (G) ≥1. Hence 1 ≤ γ _cme  (G) ≤ p - 1. □

Remark 1. For the path P₃, γ _cme  (P₃) =1 and for the complete graph K₂, γ _cme  (K₂) =1 = p - 1. Thus the bounds in Theorem 4 are sharp. Also, all the inequalities in Theorem 4 are strict. For the graph G given in Fig. 1, γ _cme  (G) =3 so that 1 < γ _cme  < p - 1 .

Theorem 5. For any tree T, rad _m  (T) ≤ γ _cme  (T) ≤ diam _m  (T) +1.

Proof. Let r = rad _m  (T) and d = diam _m  (T). Let P : v₀, v₁, …, v _r , v_r+1, …, v _d be a diametral path of T. Then the vertex v₀ is the monophonic eccentric vertex of u with d _m  (v₀, u) ≥ r and the vertex v _d is the monophonic eccentric vertex of u with d _m  (u, v _d ) ≥ r. If deg (v _i ) =2 (1 ≤ i ≤ r - 1), then S = {v₀, v₁, …, v_r-1} is a minimum CMED-set of T. Otherwise, S is a subset of a minimum CMED-set of T. Hence γ _cme  (T) ≥ rad _m  (T). Also, V (P) is a CMED-set of T and so γ _cme  (T) ≤ diam _m  (T) +1. □

Theorem 6. Let G = K _n  + H, where H is any connected graph. Then γ _cme  (G) = γ _cme  (H).

Proof. Let S be a minimum CMED-set of H and let v₁, v₂, …, v _n be the vertices of K _n . Clearly, any vertex in H is a monophonic eccentric vertex of v _i (1 ≤ i ≤ n). Since the vertices v _i (1 ≤ i ≤ n) are adjacent to every vertex of H, any monophonic eccentric vertex of a vertex, say u, in H is again a monophonic eccentric vertex of u in G. Hence S is also a minimum CMED-set of G and so γ _cme  (G) = γ _cme  (H) . □

Theorem 7. Let G be a monophonic self-centered graph with rad _m  (G) =2 and let S be a minimum CMED-set of G. Then the induced subgraph does not lie on a triangle if and only if γ _cme  (G) =2 .

Proof. Let G be a monophonic self-centered graph with rad _m  (G) =2 and let S be a minimum CMED-set of G. Assume that the induced subgraph does not lie on a triangle. Since rad _m  (G) =2, no single vertex set form a minimum CMED-set of G. Then we choose any two adjacent vertices, say x and y, which are not in a triangle. Clearly, the vertex x is a monophonic eccentric vertex of every vertex in V - N (x). Similarly, the vertex y is a monophonic eccentric vertex of every vertex in V - N (y). Thus S = {x, y} is a minimum CMED-set of G and so γ _cme  (G) =2 . Conversely, assume that γ _cme  (G) =2 . Suppose the induced subgraph lies in a triangle. Let the remaining vertex of the triangle be u. Since G is a monophonic self-centered graph with rad _m  (G) =2, u has no monophonic eccentric vertex in S, which is a contradiction. Thus the induced subgraph does not lie on a triangle.□

Theorem 8. For the complete graph K _p   (p ≥ 2), γ _me  (K _p ) = γ _cme  (K _p ) =1.

Proof. Since every vertex of K _p   (p ≥ 2) is a monophonic eccentric vertex of other vertices in K _p , any single vertex set, say S, is a minimum MED-set of K _p and its induced subgraph is connected. Thus γ _me  (K _p ) = γ _cme  (K _p ) =1. □

Theorem 9. If P is a path of order p ≥ 2, then γ cme ( P ) = ⌈ p - 1 2 ⌉ .

Proof. Let P : v₁, v₂, …, v _p be a path of order p ≥ 2. If p is odd, let p = 2k + 1, where k is a positive integer. Then {v₁, v₂, …, v _k } and {v_k+2, v_k+3, …, v_2k+1} are the minimum CMED-sets of P and so γ cme ( P ) = k = p - 1 2 = ⌈ p - 1 2 ⌉ . If p is even, let p = 2k, where k is a positive integer. Then {v₁, v₂, …, v _k } and {v_k+1, v_k+2, …, v_2k} are the minimum CMED-sets of P and so γ cme ( P ) = k = p 2 = ⌈ p - 1 2 ⌉ .□

Theorem 10. For the complete bipartite graph K_r,s, γ cme ( K r , s ) = { 1 if r = 1 or s = 1 2 if r , s ≥ 2 .

Proof. Let V₁ = {u₁, u₂, . . . , u _r } and V₂ = {v₁, v₂, . . . , v _s } be the partite sets of K_r,s.

Case 1. r = 1 or s = 1.

If r = 1, let S = {v _i } (1 ≤ i ≤ s) and if s = 1, let S = {u _j } (1 ≤ j ≤ r). Clearly, S is a minimum CMED-set of K_r,s and so γ _cme  (K_r,s) =1.

Case 2. r, s ≥ 2.

Clearly, no single vertex set is a minimum CMED-set of K_r,s. Let S = {u _i , v _j } (1 ≤ i ≤ r, 1 ≤ j ≤ s). It can be easily seen that every vertex in V₁ - {u _i } has a monophonic eccentric vertex u _i (1 ≤ i ≤ r) and every vertex in V₂ - {v _j } has a monophonic eccentric vertex v _j (1 ≤ j ≤ s). Since is connected, S is a minimum CMED-set of K_r,s. Thus γ _cme  (K_r,s) =2.□

Theorem 11. If G is a cycle with order p ≤ 8, then γ _me  (G) = γ _cme  (G).

Proof. Let G be a cycle with order p ≤ 8. If p = 3, then G = K₃ and hence by Theorem 8, γ _cme  (G) =1. If 3 < p < 7, then any two adjacent vertices of G will form a minimum CMED-set of G and so γ _cme  (G) =2. If p = 7 or 8, then any ⌈ p - 1 2 ⌉ consecutive vertices will form a minimum CMED-set of G and so γ cme ( G ) = ⌈ p - 1 2 ⌉ . Hence in all cases, by Theorem 1, we have γ _me  (G) = γ _cme  (G) .□

Theorem 12. If G is a cycle with order p ≥ 6, then γ _cme  (G) = p - 4 = diam _m  (G) -2.

Proof. Since G is a cycle of order p ≥ 6, any p - 4 consecutive vertices will form a minimum CMED-set of G and so γ _cme  (G) = p - 4. Since the monophonic diameter of any cycle of order p is p - 2, we have γ _cme  (G) = diam _m  (G) -2 .□

Theorem 13. If G is a cycle with order p > 8, then γ _me  (G) < γ _cme  (G).

Proof. It follows from Theorems 1 and 12.□

Theorem 14. If G is a wheel with order p ≤ 9, then γ _me  (G) = γ _cme  (G).

Proof. Let G = W _p  = C_p-1 + K₁ be a wheel with order p ≤ 9. Let v₁, v₂, …, v_p-1 be the vertices of C_p-1 and let u be the vertex of K₁. Clearly, the monophonic central vertex u does not belong to any minimum MED-set of G. If p = 4, then G = K₄ and so by Theorem 8, we have γ _me  (G) = γ _cme  (G) =1. If 4 < p < 8, then any two adjacent vertices of C_p-1 will form a minimum CMED-set of G and so γ _cme  (G) =2. If p = 8 or 9, then any ⌈ p - 2 2 ⌉ consecutive vertices of C_p-1 will form a minimum CMED-set of G and so γ cme ( G ) = ⌈ p - 2 2 ⌉ . Hence in all cases, by Theorem 2, we have γ _me  (G) = γ _cme  (G).□

Theorem 15. If G is a wheel with order p ≥ 7, then γ _cme  (G) = p - 5 = diam _m  (G) -2.

Proof. Let G = W _p  = C_p-1 + K₁ be a wheel with order p ≥ 7. Let v₁, v₂, …, v_p-1 be the vertices of C_p-1 and let u be the vertex of K₁. It is clear that the monophonic central vertex u does not belong to any minimum CMED-set of G. Then any p - 5 consecutive vertices of C_p-1 will form a minimum CMED-set of G and so γ _cme  (G) = p - 5. Since the monophonic diameter of any wheel of order p is p - 3, we have γ _cme  (G) = diam _m  (G) -2 .□

Theorem 16. For the Petersen graph G, γ _me  (G) = γ _cme  (G) =2.

Proof. It can be easily verify that any vertex v in the Petersen graph G has monophonic eccentricity 4 and any non-adjacent vertex of v is a monophonic eccentric vertex of v. Then a set containing any two adjacent vertices of G will form a minimum CMED-set of G and hence γ _cme  (G) =2.□

Theorem 17. If G = K₁ + ∪ m _j K _j , then γ cme ( G ) = { 3 if j ≥ 2 and ∑ m j ≥ 2 1 otherwise .

Proof. Let G = K₁ + ∪ m _j K _j and let x be the vertex of K₁.

Case 1. j ≥ 2 and  ∑m _j  ≥ 2.

Clearly, x is not a monophonic eccentric vertex of any vertex in G. Since ∑m _j  ≥ 2, G - x has at least two components. Let u be a monophonic eccentric vertex of some vertex in G. Then u is a vertex of a component, say G₁, of G - x. Since j ≥ 2, G₁ has at least one more vertex other than u, say v. Since G₁ is a complete graph, we have d _m  (u, v) =1. Also, since G has two or more components, we have u is not a monophonic eccentric vertex of v. Hence a MED-set of G contains at least two vertices. Let S = {u, w}, where u and w belong to two different components, say G₁ and G₂, respectively. Then the vertex u is a monophonic eccentric vertex of every vertex in G - G₁ and the vertex w is a monophonic eccentric vertex of every vertex in G - G₂. But the induced subgraph is not connected. Next, we choose a set S₁ = S ∪ {x} . It is clear that x is a common neighbor of both u and w. Hence S₁ is a minimum CMED-set of G and so γ _cme  (G) =3.

Case 2. j = 1 and  ∑m _j  ≥ 2.

The graph G contains at least one end vertex, say v. It is clear that the vertex v is the monophonic eccentric vertex of every vertex in G - v and so γ _cme  (G) =1.

Case 3.   j ≥ 1 and  ∑m _j  = 1.

The graph G = K₁ + ∪ m _j K _j is a complete graph. Then by Theorem 8, γ _cme  (G) =1.□

Remark 2. The converse of Theorem 17 is not true. For the graph G = K₁ + ∪ m _j P₃, γ _cme  (G) is 1 or 3 according as ∑m _j is 1 or more. However, G ≠ K₁ + ∪ m _j K _j .

The corona of two graphs G₁ and G₂ is G₁ o G₂ which is made up of one copy of G₁ and |V (G₁) | copies of G₂, where i ^th vertex of G₁ is adjacent to every vertex in the i ^th copy of G₂. Next theorem gives the CMED-number of the corona product of two non-trivial paths.

Theorem 18. If G = P _r o P _s   (r ≥ 2), then γ cme ( G ) = { ( s + 1 ) ⌊ r 2 ⌋ if ( r < 6 and 1 ≤ s ≤ 6 - ⌊ r + 4 2 ⌋ ) or ( r ≥ 6 and s = 1 ) r + 2 if ( r < 6 and 6 - ⌊ r + 4 2 ⌋ < s ≤ ⌊ r + 6 2 ⌋ ) or ( r ≥ 6 and 2 ≤ s ≤ ⌊ r + 6 2 ⌋ ) r + 3 if r is odd and s = r + 7 2 4 s - r - 12 if r ≥ 4 and s = ⌈ r + 8 2 ⌉ , ⌈ r + 10 2 ⌉ , ⌈ r + 12 2 ⌉ , … , r + 2 3 r - 2 if s = r + 3 3 r if s > r + 3 .

Proof. In G = P _r o P _s , let u₁, u₂, …, u _r (r ≥ 2) be the vertices of P _r and v_i,1, v_i,2, …, v_i,s be the vertices of the i ^th copy of P _s (1 ≤ i ≤ r).

Case 1. (r < 6 and 1 ≤ s ≤ 6 - ⌊ r + 4 2 ⌋ ) or (r ≥ 6 and s = 1).

Let S = { u 1 , v 1 , 1 , … , v 1 , s ; u 2 , v 2 , 1 , … , v 2 , s ; … ; u ⌊ r 2 ⌋ , v ⌊ r 2 ⌋ , 1 , … , v ⌊ r 2 ⌋ , s } . Clearly, the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r ) and v_i,j ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r , 1 ≤ j ≤ s ) . Also, the induced subgraph is connected. Hence S is a minimum CMED-set of G and so γ cme ( G ) = ( s + 1 ) ⌊ r 2 ⌋ .

Case 2. (r < 6 and 6 - ⌊ r + 4 2 ⌋ < s ≤ ⌊ r + 6 2 ⌋ ) or (r ≥ 6 and 2 ≤ s ≤ ⌊ r + 6 2 ⌋ ) .

Clearly, the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r ) and v_i,j ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r , 1 ≤ j ≤ s ) . Also, the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ ⌊ r 2 ⌋ ) and v_i,j ( 1 ≤ i ≤ ⌊ r 2 ⌋ , 1 ≤ j ≤ s ) . Hence S = {v_1,j, v_r,j} (1 ≤ j ≤ s) is a minimum MED-set of G, but the induced subgraph is not connected. It can be easily verify that is a minimum CMED-set of G and so γ _cme  (G) = r + 2 .

Case 3. r is odd and s = r + 7 2 .

Clearly, the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ r - 1 2 ) and v_i,j ( 1 ≤ i ≤ r - 1 2 , 1 ≤ j ≤ s ) , the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( r + 3 2 ≤ i ≤ r ) and v_i,j ( r + 3 2 ≤ i ≤ r , 1 ≤ j ≤ s ) , the vertices v_1,j and v_r,j are the monophonic eccentric vertices of u r + 1 2 and v r + 1 2 , l (2 ≤ l ≤ s - 1). Also, the vertex v r + 1 2 , s is a monophonic eccentric vertex of v r + 1 2 , 1 and hence S = { v 1 , j , v r , j , v r + 1 2 , s } (1 ≤ j ≤ s) is a minimum MED-set of G, but is not connected. It can be easily verify that is a minimum CMED-set of G and so γ _cme  (G) = r + 3 .

Case 4. r ≥ 4 and s = ⌈ r + 8 2 ⌉ , ⌈ r + 10 2 ⌉ , ⌈ r + 12 2 ⌉ , … , r + 2 .

Subcase (i) r is even.

Let m = s - r + 6 2 . Clearly, the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ r 2 ) and v_i,j ( 1 ≤ i ≤ r 2 - m , 1 ≤ j ≤ s ) , the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( r + 2 2 ≤ i ≤ r ) and v_i,j ( r + 2 2 + m ≤ i ≤ r , 1 ≤ j ≤ s ) , the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of v r + 2 2 - m , l (2 ≤ l ≤ s - 1), the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of v r 2 + m , l (2 ≤ l ≤ s - 1), the vertex v r + 2 2 - m , 1 is the monophonic eccentric vertex of v r + 2 2 - m , s and the vertex v r 2 + m , 1 is the monophonic eccentric vertex of v r 2 + m , s . Also, the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( r + 4 2 - m ≤ k ≤ r 2 , 1 ≤ l ≤ m + k - r 2 ) , the vertex v_r,j is a monophonic eccentric vertex of v_k,l ( r + 4 2 - m ≤ k ≤ r 2 , m + k - r 2 + 1 ≤ l ≤ r - k + 3 ) , the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( r + 4 2 - m ≤ k ≤ r 2 , r - k + 4 ≤ l ≤ s ) , the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( r + 2 2 ≤ k ≤ r - 2 2 + m , 1 ≤ l ≤ s - k - 2 ) , the vertex v_1,j is a monophonic eccentric vertex of v_k,l ( r + 2 2 ≤ k ≤ r - 2 2 + m , s - k - 1 ≤ l ≤ k + 2 ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( r + 2 2 ≤ k ≤ r - 2 2 + m , k + 3 ≤ l ≤ s ) . Hence S = { v 1 , j , v r , j , v r + 2 2 - m , 1 , v r 2 + m , 1 } ∪ { v r + 4 2 - m , 1 , v r + 6 2 - m , 1 , … , v r 2 , 1 ; v r + 4 2 - m , s , v r + 6 2 - m , s , … , v r 2 , s } ∪ { v r + 2 2 , 1 , v r + 4 2 , 1 , … , v r - 2 2 + m , 1 ; v r + 2 2 , s , v r + 4 2 , s , … , v r - 2 2 + m , s } is a minimum MED-set of G, but is not connected. It can be easily verify that is a minimum CMED-set of G and so γ cme ( G ) = ( r + 4 ) + 4 ( m - 1 ) = r + 4 + 4 ( s - r + 6 2 - 1 ) = r + 4 + 2 ( 2 s - r - 6 - 2 ) = 4 s - r - 12 .

Subcase (ii) r is odd.

Let m = s - r + 7 2 . Clearly, the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ r - 1 2 ) and v_i,j ( 1 ≤ i ≤ r - 1 2 - m , 1 ≤ j ≤ s ) , the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( r + 3 2 ≤ i ≤ r ) and v_i,j ( r + 3 2 + m ≤ i ≤ r , 1 ≤ j ≤ s ) , the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of v r + 1 2 - m , l (2 ≤ l ≤ s - 1), the vertex v_1,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of v r + 1 2 + m , l (2 ≤ l ≤ s - 1), the vertex v r + 1 2 - m , 1 is the monophonic eccentric vertex of v r + 1 2 - m , s , the vertex v r + 1 2 + m , 1 is the monophonic eccentric vertex of v r + 1 2 + m , s . Also, the vertices v_1,j and v_r,j are the monophonic eccentric vertices of u r + 1 2 and v r + 1 2 , j (m + 2 ≤ j ≤ s - m - 1), the vertex v r + 1 2 , s is the monophonic eccentric vertex of v r + 1 2 , j (1 ≤ j ≤ m + 1) and the vertex v r + 1 2 , 1 is the monophonic eccentric vertex of v r + 1 2 , j (s - m ≤ j ≤ s), the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( r + 3 2 - m ≤ k ≤ r - 1 2 , 1 ≤ l ≤ m + k - r - 1 2 ) , the vertex v_r,j is a monophonic eccentric vertex of v_k,l ( r + 3 2 - m ≤ k ≤ r - 1 2 , m + k - r - 3 2 ≤ l ≤ r - k + 3 ) , the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( r + 3 2 - m ≤ k ≤ r - 1 2 , r - k + 4 ≤ l ≤ s ) , the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( r + 3 2 ≤ k ≤ r - 1 2 + m , 1 ≤ l ≤ s - k - 2 ) , the vertex v_1,j is a monophonic eccentric vertex of v_k,l ( r + 3 2 ≤ k ≤ r - 1 2 + m , s - k - 1 ≤ l ≤ k + 2 ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( r + 3 2 ≤ k ≤ r - 1 2 + m , k + 3 ≤ l ≤ s ) . Hence S = { v 1 , j , v r , j , v r + 1 2 - m , 1 , v r + 1 2 + m , 1 , v r + 1 2 , 1 , v r + 1 2 , s } ∪ { v r + 3 2 - m , 1 , v r + 5 2 - m , 1 , … , v r - 1 2 , 1 ; v r + 3 2 - m , s , v r + 5 2 - m , s , … , v r - 1 2 , s } ∪ { v r + 3 2 , 1 , v r + 5 2 , 1 , … , v r - 1 2 + m , 1 ; v r + 3 2 , s , v r + 5 2 , s , … , v r - 1 2 + m , s } is a minimum MED-set of G, but is not connected. It can be easily verify that is a minimum CMED-set of G and so γ cme ( G ) = ( r + 6 ) + 4 ( m - 1 ) = r + 6 + 4 ( s - r + 7 2 - 1 ) = r + 6 + 2 ( 2 s - r - 7 - 2 ) = 4 s - r - 12 .

Case 5. s = r + 3.

Clearly, the vertex v_r,j (1 ≤ j ≤ s) is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ ⌊ r 2 ⌋ ) and v_k,l ( 1 ≤ k ≤ ⌊ r 2 ⌋ , k + 1 ≤ l ≤ s - k ) , the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( 1 ≤ k ≤ ⌊ r 2 ⌋ , 1 ≤ l ≤ k ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( 1 ≤ k ≤ ⌊ r 2 ⌋ , s + 1 - k ≤ l ≤ s ) . Also, the vertex v_1,j is a monophonic eccentric vertex of u _i ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r ) and v_k,l ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r , r - k + 2 ≤ l ≤ k + 2 ) , the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r , 1 ≤ l ≤ r - k + 1 ) , the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( ⌊ r 2 + 1 ⌋ ≤ i ≤ r , k + 3 ≤ l ≤ s ) . Hence S = {v_1,1, v_2,1, …, v_r,1} ∪ {v_2,s, v_3,s, …, v_r-1,s} is a minimum MED-set of G, but is not connected. It can be easily verify that is a minimum CMED-set of G and so γ _cme  (G) = r + r + r - 2 =3r - 2 .

Case 6. s > r + 3.

Let m = ⌈ s - ( r + 3 ) 2 ⌉ . If r is even, then the vertex v_r,j is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ r 2 ) and the vertex v_1,j is a monophonic eccentric vertex of u _i ( r + 2 2 ≤ i ≤ r ) . In 1 ≤ k ≤ r 2 , if m + k ≤ r + 2 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l (1 ≤ l ≤ s + k - r - 3), the vertex v_r,j is a monophonic eccentric vertex of v_k,l (s + k - r - 2 ≤ l ≤ r + 3 - k), and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l (r + 4 - k ≤ l ≤ s). In 1 ≤ k ≤ r 2 , if m + k > r + 2 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( 1 ≤ l ≤ ⌊ s + 1 2 ⌋ ) and the vertex v_k,1 is a monophonic eccentric vertex of v_k,l ( ⌊ s + 3 2 ⌋ ≤ l ≤ s ) . In r + 2 2 ≤ k ≤ r , if k - m ≥ r 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l (1 ≤ l ≤ s - k - 2), the vertex v_1,j is a monophonic eccentric vertex of v_k,l (s - k - 1 ≤ l ≤ k + 2) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l (k + 3 ≤ l ≤ s). In r + 2 2 ≤ k ≤ r , if k - m < r 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( 1 ≤ l ≤ ⌊ s + 1 2 ⌋ ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( ⌊ s + 3 2 ⌋ ≤ l ≤ s ) .

If r is odd, then the vertex v_r,j is a monophonic eccentric vertex of u _i ( 1 ≤ i ≤ r - 1 2 ) , the vertices v_1,j and v_r,j are the monophonic eccentric vertices of u r + 1 2 and the vertex v_1,j is a monophonic eccentric vertex of u _i ( r + 3 2 ≤ i ≤ r ) . In 1 ≤ k ≤ r + 1 2 , if m + k ≤ r + 1 2 , then the vertex v_k,s is a monophonic eccentric vertex of v_k,l (1 ≤ l ≤ s + k - r - 3), the vertex v_r,j is a monophonic eccentric vertex of v_k,l ( 1 ≤ k ≤ r - 1 2 , s + k - r - 2 ≤ l ≤ r + 3 - k ) , the vertices v_1,j and v_r,j are the monophonic eccentric vertices of v r + 1 2 , l (s + k - r - 2 ≤ l ≤ r + 3 - k) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l (r + 4 - k ≤ l ≤ s). In 1 ≤ k ≤ r + 1 2 , if m + k > r + 1 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( 1 ≤ l ≤ ⌊ s + 1 2 ⌋ ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( ⌊ s + 3 2 ⌋ ≤ l ≤ s ) . In r + 3 2 ≤ k ≤ r , if k - m ≥ r + 1 2 , then the vertex v_k,s is a monophonic eccentric vertex of v_k,l (1 ≤ l ≤ s - k - 2), the vertex v_1,j is a monophonic eccentric vertex of v_k,l (s - k - 1 ≤ l ≤ k + 2) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l (k + 3 ≤ l ≤ s). In r + 3 2 ≤ k ≤ r , if k - m < r + 1 2 , then the vertex v_k,s is the monophonic eccentric vertex of v_k,l ( 1 ≤ l ≤ ⌊ s + 1 2 ⌋ ) and the vertex v_k,1 is the monophonic eccentric vertex of v_k,l ( ⌊ s + 3 2 ⌋ ≤ l ≤ s ) . Hence S = {v_1,1, v_2,1, …, v_r,1} ∪ {v_1,s, v_2,s, …, v_r,s} is a minimum MED-set of G, but is not connected. It can be easily verify that is a minimum CMED-set of G and so γ _cme  (G) = r + r + r = 3r .□

Example 2. When r = 2 and s = 3, the corona product graph G = P₂ o P₃ is shown in Fig. 2. It is clear that v_1,j (1 ≤ j ≤ 3) is a monophonic eccentric vertex of u₂ and v_2,j (1 ≤ j ≤ 3), and v_2,j (1 ≤ j ≤ 3) is a monophonic eccentric vertex of u₁ and v_1,j (1 ≤ j ≤ 3). Also, S = {u₁, v_1,1, v_1,2, v_1,3} is a minimum CMED-set of G and so γ cme ( G ) = 4 = ( s + 1 ) ⌊ r 2 ⌋ .

OPEN IN VIEWER

Fig. 2

The corona product graph G = P₂ o P₃ with γ _cme  (G) =4.

Remark 3. Let G = P₁ o P _s . Then

γ cme ( G ) = { 1 if s ≤ 3 2 if 3 < s < 6 3 if s ≥ 6 .

Theorem 19 If n and p are integers such that 1 ≤ n ≤ p - 1 and p - 5l - 2 ≥0, where l = ⌊ n 2 ⌋ , then there exists a connected graph G with order p and the CMED-number n.

Proof. If n = 1, let G be a complete graph with order p. Then by Theorem 8, γ _cme  (G) =1. If n = 2, let G = K_r,s (r, s ≥ 2 and r + s = p). Then by Theorem 10, γ _cme  (G) =2. Now, let n ≥ 3 and let l = ⌊ n 2 ⌋ .

Case 1. n = 2l.

Let C _i  : u _i , v _i , w _i , x _i , y _i , u _i (1 ≤ i ≤ l) be l copies of a cycle with order 5 and let K_1,p-5l-1 be a star with the cut-vertex x and the set of end vertices Z = {z₁, z₂, …, z_p-5l-1}. Form the graph G from the cycles C _i (1 ≤ i ≤ l) and the star K_1,p-5l-1 by (i) joining every vertex in C _i (1 ≤ i ≤ l) with the vertex x in K_1,p-5l-1, and (ii) joining the vertices v _l and x _l in C _l . Then the graph G has order p and is shown in Fig. 3.

OPEN IN VIEWER

Fig. 3

The graph G in Case 1 of Theorem 19.

Clearly, for any vertex v in C _i (1 ≤ i ≤ l - 1), e _m  (v) =3; for any vertex v in {u _l , w _l , y _l }, e _m  (v) =3; for any vertex v in Z ∪ {v _l , x _l }, e _m  (v) =2; and for the vertex x, e _m  (x) =1. Therefore, any two non-adjacent vertices in C _i (1 ≤ i ≤ l - 1) are mutual monophonic eccentric vertices, every vertex in C _i (1 ≤ i ≤ l) is a monophonic eccentric vertex of any vertex in Z and every vertex in V (G) - {x} is a monophonic eccentric vertex of x in G. Hence it is verify that S = ( ⋃ i = 1 l - 1 { u i , y i } ) ∪ { x , w l } is a minimum CMED-set of G and so γ _cme  (G) =2l = n .

Case 2. n = 2l + 1.

Let C _i  : u _i , v _i , w _i , x _i , y _i , u _i (1 ≤ i ≤ l - 1) be l - 1 copies of a cycle with order 5. Let P : v₁, v₂, …, v₆ be a path with order 6 and let K_1,p-5l-2 be a star with the cut-vertex x and the set of end vertices Z = {z₁, z₂, …, z_p-5l-2}. Form the graph G from the cycles C _i (1 ≤ i ≤ l - 1), the path P and the star K_1,p-5l-2 by joining every vertex in C _i (1 ≤ i ≤ l - 1) with the vertex x in K_1,p-5l-2, and joining every vertex in P with the vertex x in K_1,p-5l-2. Then the graph G has order p and is shown in Fig. 4.

OPEN IN VIEWER

Fig. 4

The graph G in Case 2 of Theorem 19.

    Clearly, the monophonic eccentricity of the vertex v _i (i = 1, 6) in P is 5, the monophonic eccentricity of the vertex v _i (i = 2, 5) in P is 4, the monophonic eccentricity of any vertex in C _i (1 ≤ i ≤ l - 1) and the vertex v _j (j = 3, 4) in P is 3, the monophonic eccentricity of any vertex in Z is 2 and the monophonic eccentricity of the vertex x is 1. Then the vertex v₆ is the monophonic eccentric vertex of v _i (i = 2, 3) in P and the vertex v₁ is the monophonic eccentric vertex of v _i (i = 4, 5) in P. Also, by an argument similar to Case 1, S = ( ⋃ i = 1 l - 1 { u i , y i } ) ∪ { v 1 , v 6 , x } is a minimum CMED-set of G and so γ _cme  (G) =2l + 1 = n .□

Next theorem gives a realization result for the ineqality rad _m  (G) +1 < diam _m  (G) with suitable conditions.

Theorem 20. For any three positive integers r, d and n ≥ 4 with r + 1 < d, there exists a connected graph G such that rad _m  (G) = r, diam _m  (G) = d and γ _cme  (G) = n.

Proof. Let C : u₁, u₂, …, u_d+2, u₁ be a cycle of order d + 2. Let H be the graph obtained from C by joining each vertex u _i (3 ≤ i ≤ d + 1) with the vertex u₁.

Case 1. r = 1.

If d = 3, let P _i  : w_i,1, w_i,2, w_i,3, w_i,4 (1 ≤ i ≤ n - 1) be n - 1 copies of a path of order 4. Let G be the graph obtained from the paths P _i (1 ≤ i ≤ n - 1) by joining every vertex in P _i (1 ≤ i ≤ n - 1) with the new vertex v. The graph G is shown in Fig. 5.

OPEN IN VIEWER

Fig. 5

The graph G in Case 1 of Theorem 20.

    It is clear to observe that 1 ≤ e _m  (x) ≤3 for any vertex x in G, e _m  (v) =1 and e _m  (w_i,1) =3 (1 ≤ i ≤ n - 1). Then rad _m  (G) =1 and diam _m  (G) =3. Also, the vertex w_i,1 is the monophonic eccentric vertex of w_i,j (1 ≤ i ≤ n - 1, j = 3 or 4) and the vertex w_k,1 (k ≠ i) is a monophonic eccentric vertex of w_i,2 (1 ≤ i ≤ n - 1). Clearly, S = ( ⋃ i = 1 n - 1 { w i , 1 } ) ∪ { v } is a minimum CMED-set of G and so γ _cme  (G) = n .

If d > 3, let P _i  : w_i,1, w_i,2, w_i,3, w_i,4 (1 ≤ i ≤ n - 3) be n - 3 copies of a path of order 4. Let G be the graph obtained from the paths P _i (1 ≤ i ≤ n - 3) and the graph H by joining every vertex in P _i (1 ≤ i ≤ n - 3) with the vertex u₁ in H. The graph G is shown in Fig. 6. It is clear to observe that 1 ≤ e _m  (x) ≤ d for any vertex x in G, e _m  (u₁) =1 and e _m  (u₂) = d. Then rad _m  (G) =1 and diam _m  (G) = d. Also, the vertex u_d+2 is the monophonic eccentric vertex of u _i ( 1 ≤ i ≤ ⌈ d + 2 2 ⌉ ) , the vertex u₂ is the monophonic eccentric vertex of u _i ( ⌈ d + 2 2 ⌉ + 1 ≤ i ≤ d + 2 ) and w_i,2 (1 ≤ i ≤ n - 3), and the vertex w_i,1 is the monophonic eccentric vertex of w_i,j (1 ≤ i ≤ n - 3, j = 3 or 4). Hence S = ( ⋃ i = 1 n - 3 { w i , 1 } ) ∪ { u 1 , u 2 , u d + 2 } is a minimum CMED-set of G and so γ _cme  (G) = n .

OPEN IN VIEWER

Fig. 6

The graph G in Case 1 of Theorem 20.

Case 2. r > 1.

Let P _i  : w_i,1, w_i,2, …, w_i,d+1 (1 ≤ i ≤ n - 3) be n - 3 copies of a path of order d + 1 and let P : v₁, v₂, …, v _r be a path of order r. Let G be the graph obtained from the paths P _i (1 ≤ i ≤ n - 3), the path P and the graph H by (i) joining every vertex in P _i (1 ≤ i ≤ n - 3) with the vertex v _r in P, (ii) identifying the vertices u₁ in H and v₁ in P, (iii) joining every vertex in P with the vertex u _d in H, and (iv) joining the vertices u₂, u_d+2 in H with the vertex v _r in P. The graph G is shown in Fig. 7. It is clear to observe that r ≤ e _m  (x) ≤ d for any vertex x in G, e _m  (u₁) = r and e _m  (u₂) = d. Then rad _m  (G) = r and diam _m  (G) = d. Also, the vertex w_i,1 is the monophonic eccentric vertex of w_i,d+1 (1 ≤ i ≤ n - 3), the vertex u₃ is the monophonic eccentric vertex of w_i,j (1 ≤ i ≤ n - 3, 2 ≤ j ≤ d), the vertex w_i,j (1 ≤ i ≤ n - 3, 1 ≤ j ≤ d + 1) is a monophonic eccentric vertex of u₁ and u _i (3 ≤ i ≤ d - 1), and the vertex u₂ is the monophonic eccentric vertex of u _i (d ≤ i ≤ d + 2). If r ≥ 3, the vertex u₂ is the monophonic eccentric vertex of v _i (2 ≤ i ≤ r - 1). It is clear that S = ( ⋃ i = 1 n - 3 { w i , 1 } ) ∪ { u 2 , u 3 , v r } is a minimum CMED-set of G and so γ _cme  (G) = n .□

OPEN IN VIEWER

Fig. 7

The graph G in Case 2 of Theorem 20.

In this paper, we identified a new parameter known as connected monophonic eccentric domination number in graphs and it has many real life applications. Several interesting results with regard to this parameter have been developed. The bounds for this parameter are determined and the same is also determined for some standard graphs. More interestingly, this parameter is determined for the Petersen graph and the corona product of two non-trivial paths. A connected graph with connected monophonic eccentric domination number 2 is characterized. Some realization theorems are developed for this parameter with suitable conditions. As for future work is concerned, this parameter can be studied with regard to other conditional domination parameters as well as fuzzy graphs.