CUBO, A Mathematical Journal Vol.22, N◦03, (315–324). December 2020 http://dx.doi.org/10.4067/S0719-06462020000300315 Received: 17 March, 2020 | Accepted: 05 October, 2020 Characterization of Upper Detour Monophonic Domination Number M. Mohammed Abdul Khayyoom Department of Mathematics PTM Govt. College, Perintalmanna, Malappuram, Kerala, India. khayyoom.m@gmail.com ABSTRACT This paper introduces the concept of upper detour monophonic domination number of a graph. For a connected graph G with vertex set V (G), a set M ⊆ V (G) is called minimal detour monophonic dominating set, if no proper subset of M is a detour monophonic dominating set. The maximum cardinality among all minimal monophonic dominating sets is called upper detour monophonic domination number and is denoted by γ+ dm (G). For any two positive integers p and q with 2 ≤ p ≤ q there is a connected graph G with γm(G) = γdm(G) = p and γ + dm (G) = q. For any three positive integers p, q, r with 2 < p < q < r, there is a connected graph G with m(G) = p, γdm(G) = q and γ+ dm (G) = r. Let p and q be two positive integers with 2 < p < q such that γdm(G) = p and γ+ dm (G) = q. Then there is a minimal DMD set whose cardinality lies between p and q. Let p, q and r be any three positive integers with 2 ≤ p ≤ q ≤ r. Then, there exist a connected graph G such that γdm(G) = p, γ + dm (G) = q and |V (G)| = r. RESUMEN Este artículo introduce el concepto de número de dominación de desvío monofónico superior de un grafo. Para un grafo conexo G con conjunto de vértices V (G), un conjunto M ⊆ V (G) se llama conjunto dominante de desvío monofónico minimal, si ningún subconjunto propio de M es un conjunto dominante de desvío monofónico. La cardinalidad máxima entre todos los conjuntos dominantes de desvío monofónico minimales se llama número de dominación de desvío monofónico superior y se denota por γ+ dm (G). Para cualquier par de enteros positivos p y q con 2 ≤ p ≤ q existe un grafo conexo G con γm(G) = γdm(G) = p y γ + dm (G) = q. Para cualquiera tres enteros positivos p, q, r con 2 < p < q < r, existe un grafo conexo G con m(G) = p, γdm(G) = q y γ+ dm (G) = r. Sean p y q dos enteros positivos con 2 < p < q tales que γdm(G) = p y c©2020 by the author. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://dx.doi.org/10.4067/S0719-06462020000300315 316 M. Mohammed Abdul Khayyoom CUBO 22, 3 (2020) γ+ dm (G) = q. Entonces existe un conjunto DMD mínimo cuya cardinalidad se encuentra entre p y q. Sean p, q y r tres enteros positivos cualquiera con 2 ≤ p ≤ q ≤ r. Entonces existe un grafo conexo G tal que γdm(G) = p, γ + dm (G) = q y |V (G)| = r. Keywords and Phrases: Monophonic number, Domination Number, Detour monophonic num- ber, Detour monophonic domination number, Upper detour monophonic domination number. 2020 AMS Mathematics Subject Classification: 05C69, 05C12. 1 Introduction Consider an undirected connected graph G(V, E) without loops or multiple edges. Let P : u1, u2, ...un be a path of G. An edge e is said to be a chord of P if it is the join of two non adjacent vertices of P . A path is said to be monophonic path if there is no chord. If S is a set of vertices of G such that each vertex of G lies on an u − v monophonic path in G for some u, v ∈ S, then S is called monophonic set. Monophonic number is the minimum cardinality among all the monophonic sets of G. It is denoted by m(G) [1,2]. A vertex v in a graph G dominates itself and all its neighbours. A set T of vertices in a graph G is a dominating set if N[T ] = V (G). The minimum cardinality among all the dominating sets of G is called domination number and is dented by γ(G)[4]. A set T ⊂ V (G) is a monophonic dominating set of G if T is both monophonic set and dominating set. The monophonic domination number is the minimum cardinality among all the monophonic dominating sets of G and is denoted by γm(G)[5,6]. A monophonic set M in a connected graph G is minimal monophonic set if no proper subset of M is a monophonic set. The upper monophonic number is the maximum cardinality among all minimal monophonic sets and is denoted by m+(G)[9]. The shortest x − y path is called geodetic path and longest x − y monophonic path is called detour monophonic path. If every vertex of G lies on a x−y detour monophonic path in G for some x, y ∈ M ⊆ V (G), M could be identified as a detour monophonic set. The minimum cardinality among all the detour monophonic set is the detour monophonic number and is denoted by dm(G). A minimal detour monophonic set D of a connected graph G is a subset of V (G) whose any proper subset is not a detour monophonic set of G. The maximum cardinality among all minimal detour monophonic sets is called upper detour monophonic set, denoted by dm+(G) [10]. If D is both a detour monophonic set and a dominating set, it could be a detour monophonic dominating set. The minimum cardinality among all detour monophonic dominating sets of G is the detour monophonic dominating number ( DMD number) and is denoted by γdm(G)[7,8]. A vertex v is an extreme vertex if the sub graph induced by its neighbourhood is complete. A vertex u in a connected graph G is a cut-vertex of G, if G − u is disconnected. In this article, we consider CUBO 22, 3 (2020) Characterization of Upper Detour Monophonic Domination Number 317 G as a connected graph of order n ≥ 2 if otherwise not stated. For basic notations and terminology refer [3]. Theorem 1.1 (8). Each extreme vertex of a connected graph G belongs to every detour monophonic dominating set of G. Example 1.1. Consider the graph G given in Figure 1. Here M1 = {v1, v4} is a monophonic set. Therefore m(G) = 2. M1 also dominate G. Hence γ(G) = 2. The set M2 = {v1, v2, v3} is a minimum detour monophonic set. Thus dm(G) = 3. M2 does not dominate G. M2 ∪ {v4} is a minimum DMD set. Therefore γdm(G) = 4. 2 UDMD Number of a Graph Definition 2.1. A detour monophonic dominating set M in a connected graph G is called minimal detour monophonic dominating set if no proper subset of M is a detour monophonic dominating set. The maximum cardinality among all minimal detour monophonic dominating sets is called upper detour monophonic domination number and is denoted by γ+ dm (G). Figure 1: Graph G with UDMD number 5 Example 2.1. Consider the graph G given in Figure 1. The set M = {v1, v5, v6, v7, v8} is a minimal DMD set with maximum cardinality. Therefore γ+ dm (G) = 5. Theorem 2.1. Let G be a connected graph and v an extreme vertex of G. Then v belongs to every minimal detour monophonic dominating set of G. Proof. Every minimal detour monophonic dominating set is a minimum detour monophonic set. Since each extreme vertex belongs to every minimum detour monophonic dominating set, the result follows. 318 M. Mohammed Abdul Khayyoom CUBO 22, 3 (2020) Theorem 2.2. Let v be a cut- vertex of a connected graph G. If M is a minimal DMD set of G, then each component of G − v have an element of M. Proof. Suppose let A is a component of G − v having no vertices of M. Let u be any one of the vertex in A. Since M is a minimal DMD set, there exist two vertices p, q in M such that u lies on a p − q detour monophonic path P : p, u0, u1, ..., u, ..., um = q in G. Consider two sub-paths P1 : p − u and P2 : u − q of P . Given v is a cut-vertex of G. Therefore both P1 and P2 contain v. Hence P is not a path. This is a contradiction. That is, each component of G − v have an element of every minimal DMD set. Theorem 2.3. For a connected graph G of order n, γdm(G) = n if and only if γ + dm (G) = n. Proof. First, suppose γ+ dm (G) = n. That is M = V (G) is the unique minimal DMD set of G, so that no proper subset of M is a DMD set. Hence M is the unique DMD set. Therefore γdm(G) = n. Conversely, let γdm(G) = n. Since every DMD set is a minimal DMD set, γdm(G) ≤ γ + dm (G). Therefore γ+ dm (G) ≥ n. Since V (G) is the maximum DMD set, γ+ dm (G) = n. 3 UDMD Number of Some Standard Graphs Example 3.1. Complete bipartite graph Km,n For complete bipartite graph G = Km,n, γ+ dm (G) =          2, if m = n = 1; n, if n ≥ 2, m = 1; 4, if m = n = 3 max{m, n} if m, n ≥ 2, m, n 6= 3 Proof. Case (i): Let m = n = 1. Then Km,n = K2. Therefore γ + dm (G) = 2. Case (ii): Let n ≥ 2, m = 1. This graph is a rooted tree. There are n end vertices. All these are extreme vertices. Therefore they belong to every DMD set and consequently every minimal DMD set. Case (iii): If m = n = 3, then exactly two vertices from both the particians form a minimal DMD set. Case (iv): Let m, n ≥ 2, m, n 6= 3. Assume that m ≤ n. Let A = {a1, a2, ...am} and B = {b1, b2, ...bn} be the partitions of G. First, prove M = B is a minimal DMD set. Take a vertex aj, 1 ≤ j ≤ m, which lies in a detour monophonic path biajbk for k 6= j so that M is a detour monophonic set. They also dominate G. Hence M is a DMD set. CUBO 22, 3 (2020) Characterization of Upper Detour Monophonic Domination Number 319 Next, let S be any minimal DMD set such that |S| > n. Then S contains vertices from both the sets A and B. Since A and B are themselves minimal DMD sets, they do not completely belongs to S. Note that if S contains exactly two vertices from A and B, then it is a minimum DMD set. Thus γ+ dm (G) = n = max{m, n}. Example 3.2. Complete graph Kn For complete graph G = Kn, γ + dm (G) = n. Proof. For a complete graph G, every vertex in G is an extreme vertex. By theorem 2.1 they belong to every minimal DMD set. Example 3.3. Cycle graph Cn For Cycle graph G = Cn with n vertices , γ+ dm (G) =        3, if n ≤ 7, n 6= 4 2, if n = 4 4 + n − 7 − r 3 , if n ≥ 8, n − 7 ≡ r mod(3) Proof. For n ≤ 7 the results are trivial. For n ≥ 8, let Cn : v1, v2, v3, ..., vn, v1 be the cycle with n vertices. Then the set of vertices {v1, v3, vn−1} is a minimal detour monophonic set but not dominating. This set dominates only seven vertices. There are n − 7 remaining vertices. If r is the reminder when n − 7 is divided by 3, then n − 7 − r 3 + 1 vertices dominate the remaining vertices. Therefore every minimal DMD set contains 4 + n − 7 − r 3 vertices. 4 Characterization of γ+dm(G) Theorem 4.1. For any two positive integers p and q with 2 ≤ p ≤ q there is a connected graph G with γm(G) = γdm(G) = p and γ + dm (G) = q. Proof. Construct a graph G as follows. Let C6 : u1, u2, u3, u4, u5, u6, u1 be the cycle of order 6. Join p−1 disjoint vertices M1 = {x1, x2, ..., xp−1} with the vertex u1. Let M2 = {y1, y2, ..., yq−p−1} be a set of q − p− 1 disjoint vertices. Add each vertex in M2 with u4 and u6. Let xp−1 be adjacent with u2 and u6. This is the graph G given in Figure 2. Since all vertices except xp−1 in M1 are extreme, they belong to every minimum monophonic dominating set and DMD set. The set M = M1 ∪ {u4} is a minimum monophonic dominating set. Therefore γm(G) = p. Moreover, the set of all vertices in M form a DMD set and is minimum. That is γdm(G) = p. 320 M. Mohammed Abdul Khayyoom CUBO 22, 3 (2020) Next, we prove that γ+ dm (G) = q. Clearly N = M1 ∪ M2 ∪ {u5, u6} is a DMD set. N is also a minimal DMD set of G. For the proof, let N′ be any proper subset of N. Then there exists at least one vertex u ∈ N and u /∈ N′. If u = yi, for 1 ≤ i ≤ q − p − 1, then yi does not lie on any x − y detour monophonic path for some x, y ∈ N′. Similarly if u ∈ {u5, u6, xp−1}, then that vertex does not lie on any detour monophonic path in N′. Thus N is a minimal DMD set. Therefore γ+ dm (G) ≥ q. Figure 2: γm(G) = γdm(G) = p and γ + dm (G) = q. Note that N is a minimal DMD set with maximum cardinality. On the contrary, suppose there exists a minimal DMD set, say T , whose cardinality is strictly greater than q. Then there is a vertex u ∈ T, u /∈ N. Therefore u ∈ {u2, u3, u4}. If u = u4, then M1 ∪ {u4} is a DMD set properly contained in T which is a contradiction. If u = u3, then the set M1 ∪ {u3, u5} is a DMD set which is a proper subset of T and is a contradiction. If u = u2, then the set (N − {u6}) ∪ {u2} is a DMD set properly contained in T and is a contradiction. Thus γ+ dm (G) = q. Theorem 4.2. For any three positive integers p, q, r with 2 < p < q < r, there is a connected graph G with m(G) = p, γdm(G) = q and γ + dm (G) = r. Proof. Let G be the graph constructed as follows. Take q − p copies of a cycle of order 5 with each cycle Ci has a vertex set {di, ei, fi, gi, hi}, for 1 ≤ i ≤ q − p. Join each ei with all other vertices in Ci. Also join the vertex fi−1 of Ci−1 with the vertex di of Ci. Let {u, v} and {b1, b2, ..., br−q+1} be two sets of mutually non adjacent vertices. Join each bi with u and v, for 1 ≤ i ≤ r − q + 1. Join another p − 2 pendent vertices with u and one pendent vertex with d1. This is the graph G given in Figure 3. The set M1 = {a0, a1, a2..., ap−2} is the set of all extreme vertices and belongs to every monophonic dominating set and DMD set (Theorem 1.1). Clearly M1 is not monophonic. But M1 ∪ {v} is a monophonic set and is minimum. Therefore m(G) = p. Take M2 = {e1, e2, ..., eq−p}. Then M1 ∪ M2 ∪ {v} is a DMD set and is minimum. Therefore γdm(G) = p − 1 + q − p + 1 = q. CUBO 22, 3 (2020) Characterization of Upper Detour Monophonic Domination Number 321 Figure 3: Graph G with m(G) = p, γdm(G) = q and γ + dm (G) = r. Let M3 = {b1, b2, ..., br−q+1}. Then M = M1 ∪ M2 ∪ M3 is a DMD set. Now M is a minimal DMD set. On the contrary, suppose N is any proper DMD subset of M so that there exists at least one vertex in M which does not belong to N. Let u ∈ M and u /∈ N. Clearly u /∈ M1 since M1 is the set of all extreme vertices. If u = ei for some i, then the vertex ei does not belong to any detour monophonic path induced by N. Therefore u /∈ M2. Similarly u /∈ M3. This is a contradiction. Hence M is a minimal DMD set with maximum cardinality. Therefore γ+ dm (G) = |M1| + |M2| + |M3| = (p − 1) + (q − p) + (r − q + 1) = r. Theorem 4.3. Let p and q be two positive integers with 2 < p < q such that γdm(G) = p and γ+ dm (G) = q. Then there is a minimal DMD set whose cardinality lies between p and q. Proof. Consider three sets of mutually disjoint vertices M1 = {a1, a2, ..., aq−n+1}, M2 = {b1, b2, ..., bn−p+1} and M3 = {x, y, z}. Join each vertex ai with x and z and each vertex bj with y and z. Add p − 2 pendent vertices M4 = {c1, c2, ..., cp−2} with the vertex y. This is the graph G given in Figure 4. Since M4 is the set of all extreme vertices, it belongs to every DMD set. But M4 is not a DMD set. The set M = M4 ∪ {x, z} is a minimum DMD set. Therefore γdm(G) = p. Consider the set N = M1 ∪ M2 ∪ M4. We claim N is a minimal DMD set with maximum cardinality. On the contrary, suppose there is a set N′ ⊂ N which is a DMD set of G. Then there exists at least one vertex, say u in N which does not belong to N′. Clearly u /∈ M4 since it is the set of all extreme vertices. If u ∈ M1, then u = ai for some i. Then the vertex ai does not lie on any detour monophonic path, which is a contradiction. Similarly, if u ∈ M2, we get a contradiction. Thus N is a minimal DMD set. Therefore γ+ dm (G) ≥ q. 322 M. Mohammed Abdul Khayyoom CUBO 22, 3 (2020) Figure 4: Graph G with γdm(G) = p and γ + dm (G) = q Next, we claim that N has the maximum cardinality of any minimal DMD set. If γ+ dm (G) > q, there is at least one vertex v ∈ V (G), v /∈ N and belongs to a minimal DMD set. Therefore v ∈ M3. If v = x, then the set M2 ∪ M4 ∪ {v} is a minimal DMD set having less than q vertices. Similarly if v = z, then the set M1 ∪ M4 ∪ {v} is a minimal DMD set. For v = y, the set N ∪ {y} is not a minimal DMD set. Therefore γ+ dm (G) ≤ q. Let n be any number which lies between p and q. Then there is a minimal DMD set of cardinality n. For the proof, consider the set T = M2 ∪ M4 ∪ {x}. T is a minimal DMD set. If T is not a minimal DMD set, there is a proper subset T ′ of T such that T ′ is a minimal DMD set. Let u ∈ T and u /∈ T ′. Since each vertex in M4 is an extreme vertex, v /∈ M4. If u = x, then the vertex u is not an internal vertex of any detour monophonic path in T ′. A similar argument may be made if u ∈ M2. This leads to a contradiction. Therefore T is a minimal DMD set with cardinality (n − p + 1) + (p − 2) + 1 = n. Theorem 4.4. Let p , q and r be any three positive integers with 2 ≤ p ≤ q ≤ r. Then, there exists a connected graph G such that γdm(G) = p, γ + dm (G) = q and |V (G)| = r. Proof. Let K1,p is a star graph with leaves set M1 = {u1, u2, ..., up} and let u be the support vertex of K1,p. Insert r − q − 1 vertices M2 = {v1, v2, ..., vr−q−1} in the edges uui respectively for 1 ≤ i ≤ r − q − 1. Add q − p vertices M3 = {x1, x2, ..., xq−p} with this graph and join each xi with u and u1. This is the graph G as shown in Figure 5. Here |V (G)| = (q −p)+p+(r −q −1)+1 = r. The length of a detour monophonic path is 4. CUBO 22, 3 (2020) Characterization of Upper Detour Monophonic Domination Number 323 Figure 5: Graph G with γdm(G) = p and γ + dm (G) = q Let T = M1 −{u1}. All the vertices in T are extreme vertices and belong to all DMD sets and minimal DMD sets. Clearly M1 is a DMD set with minimum cardinality. Therefore γdm(G) = p. Let N = T ∪ M3 ∪ {v1}. Then |N| = (p − 1) + (q − p) + 1 = q. We claim that N is a minimal DMD set with maximum cardinality. On the contrary, suppose there is a proper subset N′ of N which is a minimal DMD set of G. Then there exists at least one vertex x ∈ N, x /∈ N′. Clearly x /∈ T . If x ∈ M3, then x = xi for some i, 1 ≤ i ≤ q − p. Then the vertex xi does not lie on any u − v detour monophonic path for u, v ∈ N′. If x = v1 then v1 does not lies on any detour monophonic path in N ′. Thus no such vertex x exists. This is a contradiction. Therefore γ+ dm (G) ≥ q. To prove maximum cardinality of N, suppose there exists a minimal DMD set S with |S| > q. Since S contains T , the set of all extreme vertices, the vertex x lies on some u−v detour monophonic path for all x ∈ {u, v2, v3, .., vr−q−1}. Now S is a minimal DMD set having more than q vertices and u, v2, v3, ..., vr−q−1 /∈ S. Therefore S = {v1} ∪ M3 ∪ {u1} ∪ T . Then N is properly contained in S. This is a contradiction. Therefore γ+ dm (G) = q. Hence the proof. 324 M. Mohammed Abdul Khayyoom CUBO 22, 3 (2020) References [1] P. A. P. Sudhahar, M. M. A. Khayyoom and A. Sadiquali, “Edge Monophonic Domination Number of Graphs”. J.Adv.in Mathematics, vol. 11, no. 10, pp. 5781–5785, 2016. [2] P. A. P. Sudhahar, M. M. A. Khayyoom and A. Sadiquali, “The Connected Edge Monophonic Domination Number of Graphs”. Int. J Comp.Applications, vol. 145, no. 12, pp. 18–21, 2016. [3] G. Chartrand and P. Zhang, Introduction to Graph Theory. MacGraw Hill, 2005. [4] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundementals of Domination in Graphs. 208, Marcel Dekker Inc, New York, 1998. [5] J. Jhon and P. A. P. Sudhahar, “On The Edge Monophonic Number of a Graph Filomat”, vol. 26, no. 6, pp. 1081–1089, 2012. [6] J.Jhon and P.Arul Paul Sudhahar, “The Monophonic Domination Number of a Graph, Proceed- ings of the International Conference on Mathematics and Business Managment”, pp. 142–145, 2012. [7] M. M. A. Khayyoom and P. A. P. Sudhahar. “Edge Detour Monophonic Domination Number of a Graph. International Journal of Pure and Applied Mathematics”, vol. 120, no. 7, pp. 195–203, 2018. [8] M. M. A. Khayyoom and P. A. P. Sudhahar, “Connected Detour Monophonic Domination Number of a Graph”. Global Journal of Pure and Applied Mathematics, vol. 13, no. 5, pp. 241–249, 2017. [9] S. R. Chellathurai, and S. Padma Vijaya, “Upper Geodetic Domination Number of a Graph” Int. Journal of Cont. Math Sci., vol. 10, no. 1, pp. 23–36, 2015. [10] P. Titus, A. P. Santhakumaran, K. Ganesamoorthy, “Upper Detour Monophonic Number of a Graph”, Electronic Note in Discrete Mathematics, vol. 53, pp. 331–342, 2016. Introduction UDMD Number of a Graph UDMD Number of Some Standard Graphs Characterization of dm+(G)