For a connected graph \(G\) of order at least two, a total monophonic set of a graph \(G\) is a monophonic set \(S\) such that the subgraph \(G[S]\) induced by \(S\) has no isolated vertices. The minimum cardinality of a total monophonic set of \(G\) is the total monophonic number of \(G\) and is denoted by \(m_{t}(G)\). We determine bounds for it and characterize graphs which realize the lower bound. Also, some general properties satisfied by this concept are studied. It is shown that for positive integers \(a, b\) such that \(3 \leq a \leq b\) with \(b \leq 2a\), there exists a connected graph \(G\) such that \(m(G) = a\) and \(m_t(G) = b\). Further, if \(p, a, b\) are positive integers such that \(4 \leq a \leq b \leq p\), then there exists a connected graph \(G\) of order \(p\) with \(m_t(G) = a\) and \(m_c(G) = b\), where \(m_c(G)\) is the connected monophonic number of \(G\).
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 Harary [5]. For vertices \(x\) and y in a connected graph G, the distance \(d(x,y)\) is the length of a shortest \(x-y\) path in G. An \(x-y\) path of length \(d(x,y)\) is called an \(x-y\) geodesic [1]. The \(neighborhood\) of a vertex \(v\) is the set \(N(v)\) consisting of all vertices \(u\) which are adjacent with \(v.\) A vertex \(v\) of \(G\) is called an extreme vertex if the subgraph induced by its neighbors is complete. A vertex \(v\) of \(G\) is called a support vertex of \(G\) if it is adjacent to an end-vertex of \(G\).
A \(chord\) of a path \(P\) is an edge joining two non-adjacent vertices of \(P.\) A path \(P\) is called a monophonic path if it is a chordless path. A set \(S\) of vertices of \(G\) is a monophonic set of \(G\) if each vertex \(v\) of \(G\) lies on a \(x-y\) monophonic path for some elements \(x\) and \(y\) in \(S\). The monophonic number of \(G\) is the minimum cardinality of its monophonic sets and is denoted by \(m(G)\). The monophonic number of a graph and its related concepts were studied by several authors in [2, 3, 4, 6, 9]. A connected monophonic set of G is a monophonic set S such that the subgraph \(G[S]\) induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by \(m_c(G)\). The connected monophonic number of a graph was introduced and studied in [10]. There are useful applications of these concepts to protected facility location problems in real life situations, and also to security based communication network designs [10].
For any two vertices \(u\) and \(v\) in a connected graph \(G,\) the \(monophonic\) \(distance\) \(d_m(u,v)\) from \(u\) to \(v\) is defined as the length of a longest \(u-v\) monophonic path in \(G\). The \(monophonic\) \(eccentricity\) \(e_m(v)\) of a vertex \(v\) in \(G\) is \(e_m(v) =\) max \(\{d_m(v,u): u \in V\}\). The \(monophonic\) \(radius,\) \(rad_m(G)\) of \(G\) is \(rad_m(G)=\) min \(\{e_m(v) : v \in V\}\) and the \(monophonic\) \(diameter\), \(diam_m(G)\) of \(G\) is \(diam_m(G)=\) max \(\{e_m(v) : v \in V\}.\) The monophonic distance was introduced in [7] and further studied in [8]. This paper explores total monophonic sets as a structural extension of monophonic sets, examining properties and comparisons with other graph parameters. Future work could explore specific applications.
The following theorems will be used in the sequel.
Theorem 1.1. [9] Every extreme vertex of a connected graph \(G\) belongs to every monophonic set of \(G\). In particular, if the set \(S\) of all extreme vertices of \(G\) is a monophonic set, then \(S\) is the unique minimum monophonic set of \(G\).
Theorem 1.2. [9] Let \(G\) be a connected graph with cut-vertices and \(S\) a monophonic set of \(G\). If \(v\) is a cut-vertex of \(G\), then every component of \(G-v\) contains an element of \(S\).
Theorem 1.3. [9] For the complete graph \(K_p~(p \geq 2)\), \(m(K_p) = p\).
Theorem 1.4. [10] Every cut-vertex of a connected graph \(G\) belongs to every connected monophonic set of \(G\).
Theorem 1.5. [10] For the complete graph \(K_p~(p \geq 2)\), \(m_c(K_p) = p\).
Throughout this paper, G denotes a connected graph with at least two vertices.
Definition 2.1. A total monophonic set of a graph \(G\) is a monophonic set \(S\) such that the subgraph \(G[S]\) induced by \(S\) has no isolated vertices. The minimum cardinality of a total monophonic set of \(G\) is the total monophonic number of \(G\) and is denoted by \(m_t(G)\).
Example 2.2. For the graph \(G\) given in Figure 1, it is clear that \(S=\{u,z\}\) is the unique minimum monophonic set of \(G\) and so \(m(G)=2\). Since the subgraph induced by \(S\) has the isolated vertices \(u\) and \(z\), \(S\) is not a total monophonic set of \(G\). Also for any \(x\in V-S,\,S\cup\{x\}\) is not a total monophonic set of \(G\). Clearly, \(S_1=S\cup\{v,y\}\) is a total monophonic set of \(G\) and so \(m_t(G)=4\). Since the subgraph induced by \(S_1\) is not connected, \(S_1\) is not a connected monophonic set of \(G\). Note that \(S_1\cup\{w\}\) is a minimum connected monophonic set of \(G\) and so \(m_c(G)=5\). Thus the monophonic number, the total monophonic number and the connected monophonic number of a graph \(G\) are different.
Theorem 2.3. All the extreme vertices and support vertices of a connected graph \(G\) belong to every total monophonic set of \(G\). If the set \(S\) of all extreme vertices and support vertices of \(G\) is a total monophonic set, then it is the unique minimum total monophonic set of \(G\).
Proof. Since every total monophonic set of \(G\) is a monophonic set of \(G\), by Theorem 1.1, every extreme vertex belongs to every total monophonic set of \(G\). Since a total monophonic set of \(G\) contains no isolated vertices, it follows that every support vertex of \(G\) also belongs to every total monophonic set of \(G\). Thus, if \(S\) is the set of all extreme vertices and support vertices of \(G\), then \(m_t(G)\geq |S|\). On the other hand, if \(S\) is a total monophonic set of \(G\), then \(m_t(G)\leq|S|\). Therefore \(m_t(G)=|S|\) and \(S\) is the unique minimum total monophonic set of \(G\). ◻
Corollary 2.4. For the complete graph \(K_p (p \geq 2),\) \(m_t(G) = p\).
Remark 2.5. The converse of Corollary 2.4 need not be true. For the path \(P_4\), every vertex of \(P_4\) is either an extreme vertex or a support vertex. By Theorem 2.3, \(V(P_4)\) is the unique minimum total monophonic set of \(P_4\) and so \(m_t(P_4)=4=p\).
Theorem 2.6. Let \(G\) be a connected graph with cut-vertices and let \(S\) be a total monophonic set of \(G\). If \(v\) is a cut-vertex of \(G\), then every component of \(G-v\) contains an element of \(S\).
Proof. Since every total monophonic set of \(G\) is a monophonic set of \(G\), the result follows from Theorem 1.2. ◻
Theorem 2.7. For a connected graph \(G\) of order \(p\), \(2 \leq m(G) \leq m_t(G) \leq p\).
Proof. Any monophonic set of \(G\) needs at least two vertices and so \(m(G) \geq 2\). Every total monophonic set of \(G\) is also a monophonic set of \(G\) so that \(m(G) \leq m_t(G)\). Since \(V(G)\) induces a total monophonic set of \(G\), it is clear that \(m_t(G) \leq p\). Hence \(2 \leq m(G) \leq m_t(G) \leq p\). ◻
Corollary 2.8. Let \(G\) be a connected graph. If \(m_t(G) = 2\), then \(m(G) = 2\).
The converse of Corollary 2.8 need not be true. For the cycle \(C_5\), \(m(C_5)=2\) and \(m_t(C_5)=3\).
Remark 2.9. The bounds in Theorem 2.7 are sharp. For the complete graph \(G = K_2,\,m(G) = 2\) and for the path \(P_4\), \(m_t(P_4) =4= p\). For the graph \(G\) given in Figure 2 of order \(p=7\), it is clear that no 2-element subset of \(V(G)\) is a monophonic set of \(G\). Note that the set \(S=\{v_2,v_6,v_7\}\) is a minimum monophonic set of \(G\) and so \(m(G)=3\). Since the subgraph induced by \(S\) has an isolated vertex \(v_2\), \(S\) is not a total monophonic set of \(G\). Clearly, \(S_1=S\cup\{v_1\}\) is a minimum total monophonic set of \(G\) and so \(m_t(G)=4\). Thus, we have \(2 < m(G) <m_t(G) < p\). Hence all the inequalities in Theorem 2.7 are strict.
Theorem 2.10. For any non-trivial tree \(T\), the set of all end-vertices and support vertices of \(T\) is the unique minimum total monophonic set of \(T\).
Proof. Since the set of all end-vertices and support vertices of \(T\) form a total monophonic set, the result follows from Theorem 2.3. ◻
The next theorem gives a characterization of graphs \(G\) for which \(m_t(G)=2\).
Theorem 2.11. For any connected graph \(G\), \(m_t(G) = 2\) if and only if \(G = K_2\).
Proof. If \(G = K_2\), then \(m_t(G) = 2\). Conversely, let \(m_t(G) = 2\). Let \(S = \{u, v\}\) be a minimum total monophonic set of \(G\). Then \(uv\) is an edge. A vertex different from \(u\) and \(v\) cannot lie on a \(u-v\) monophonic path and so \(G = K_2\). ◻
Theorem 2.12. Let \(G\) be a connected graph with at least 2 vertices. Then \(m_t(G) \leq 2\, m(G)\).
Proof. Let \(S = \{v_1, v_2, \ldots, v_k\}\) be a minimum monophonic set of \(G\). Let \(u_i \in N(v_i)\) for \(i = 1, 2, \ldots, k\) and let \(T = \{u_1, u_2, \ldots, u_k\}\). Then \(S \cup T\) is a monophonic set because \(S\subseteq S \cup T\), and every vertex already lies on a monophonic path between two vertices of \(S\); also the subgraph induced by \(S \cup T\) has no isolated vertices because every \(v_i\) is adjacent to \(u_i(1\leq i\leq k)\). Hence \(S \cup T\) is a total monophonic set of \(G\) so that \(m_t(G) \leq |S \cup T| \leq 2k = 2\,m(G)\). ◻
Theorem 2.13. For a connected graph \(G\) of order \(p\), \(2 \leq m_t(G) \leq m_c(G) \leq p\).
Proof.Any total monophonic set of \(G\) needs at least two vertices and so \(m_t(G) \geq 2\). Since every connected monophonic set of \(G\) is also a total monophonic set of \(G\), it follows that \(m_t(G) \leq m_c(G)\). Since \(V(G)\) induces a connected monophonic set of \(G\), it is clear that \(m_c(G) \leq p\). Hence \(2 \leq m_t(G) \leq m_c(G) \leq p\). ◻
Remark 2.14. The bounds in Theorem 2.13 are sharp. For the complete graph \(G = K_2,\,m_t(G) = 2\) and for any path \(P_n(n\geq 2)\), \(m_c(P_n) = n\). For the graph \(G\) given in Figure 2 of order \(p=7\), Remark 2.9 shows that \(S_1\) is a minimum total monophonic set of \(G\) and so \(m_t(G)=4\). Since the subgraph induced by \(S_1\) is not connected, \(S_1\) is not a connected monophonic set of \(G\). It is clear that, \(S_1\cup\{v_5\}\) is a minimum connected monophonic set of \(G\) and so \(m_c(G)=5\). Thus, we have \(2 < m_t(G) <m_c(G) < p\). Hence all the inequalities in Theorem 2.13 are strict.
Theorem 2.15. For any connected graph \(G\), the following are equivalent
(i) \(G=K_2\)
(ii) \(m_c(G)=2\)
(iii) \(m_t(G)=2\).
Proof. The result follows from Theorems 2.11 and 2.13. ◻
Theorem 2.16. For any connected graph \(G\), \(m_t(G)=3\) if and only if \(m_c(G)=3\).
Proof. If \(m_c(G)=3\), then \(m_t(G)=2\) or 3. By Theorem 2.15, if \(m_t(G)=2\) then \(m_c(G)=2\). Hence, we have \(m_t(G)=3\). Conversely, suppose that \(m_t(G)=3\). Let \(S=\{x,y,z\}\) be a minimum total monophonic set of \(G\). Since \(S\) is a total monophonic set of \(G\), the subgraph induced by \(S\) has no isolated vertices and so \(\delta(G[S])\geq 1\). Also, hence \(|S|=3\), \(S\) is a connected monophonic set of \(G\). Hence \(m_c(G)=3\). ◻
Next, we determine the total monophonic number for some standard graphs.
Theorem 2.17. For the cycle \(C_{n}(n\geq 4)\), \(m_t(C_n)=3\).
Proof. Let \(C_{n}:v_{1}, v_{2}, v_{3}, … , v_{n},v_{1}\) be a cycle of length \(n\). Any 2-element subset of \(V(C_n)\) is not a total monophonic set of \(C_n\). Any set of three consecutive vertices of \(C_n\) is a minimum total monophonic set of \(C_n\) so that \(m_t(C_n)=3\). ◻
Theorem 2.18. For the wheel \(W_{n} = K_{1}+C_{n – 1}(n\geq 4)\), \[m_t(W_n)=\begin{cases} 4& if~ n=4\\ 3& if ~n\geq 5. \end{cases}\]
Proof. Let \(W_{n} = K_{1} + C_{n – 1}(n\geq 4)\) be the wheel with \(V(C_{n-1})=\{v_{1}, v_{2}, v_{3}, \cdots , v_{n-1},v_{1}\}\) and \(V(K_1)=\{x\}\). If \(n=4\), then \(W_4\) is the complete graph \(K_4\), and so by Corollary 2.4, \(m_t(W_4)=4\). For \(n\geq 5\), any set \(S\) of two non-adjacent vertices of \(W_n\) is a minimum monophonic set of \(W_n\). Since the subgraph induced by \(S\) has an isolated vertex, \(S\) is not a total monophonic set of \(W_n\). Any set of three consecutive vertices of \(C_{n-1}\) in \(W_n\) is a minimum total monophonic set of \(W_n\) and so \(m_t(W_n)=3\). ◻
Theorem 2.19. For the complete bipartite graph \(K_{m,n}(2\leq m\leq n )\), \[m_t(K_{m,n})=\begin{cases} 3& if~ 2=m\leq n\\ 4& if ~3\leq m\leq n. \end{cases}\]
Proof. Let \(V_{1}\) = {\(x_{1}\), \(x_{2}\),…, \(x_{m}\)} and \(V_{2}\) ={\(y_{1}\), \(y_{2}\),…,\(y_{n}\)} be the partite sets of \(K_{m,n}=G\). When \(m =2\), \(S=V_{1}\) is the unique minimum monophonic set of \(G\). Since the subgraph induced by \(S\) has the isolated vertices \(x_1\) and \(x_2\), \(S\) is not a total monophonic set of \(G\). It is clear that for any vertex \(y_i\in V_2\), \(S\cup\{y_i\}\) for some \(i\,(i\leq i\leq n)\), is a minimum total monophonic set of \(G\) and so \(m_t(G)=3\).
Now, let \(m\geq 3\). Then \(S'=\{x_{1},x_{2},y_{1},y_{2}\}\) is clearly a total monophonic set of \(G\), and it follows that \(m_t(G)\leq 4\). It is enough to show that no 3-element subset of \(V(G)\) forms a total monophonic set of \(G\). Let \(X\) be a 3-element subset of \(V(G)\). If \(m=3\) and \(X\subseteq V_1\), then it is clear that \(X\) is a monophonic set of \(G\) and the subgraph induced by \(X\) has isolated vertices. Hence \(X\) is not a total monophonic set of \(G\). If \(m\geq 4\) and \(X\subseteq V_1\). Since \(X\) contains three elements from \(V_{1}\), there exists an element \(u\in V_1\) and \(u\notin X\). Since the vertex \(u\) is not an internal vertex of any \(v-w\) monophonic path, for some elements \(v\) and \(w\) in \(X\), \(X\) is not a monophonic set of \(G\). Therefore, we may take that \(X\cap V_1=\{x_i,x_j\}\) and \(X\cap V_2=\{y_k\}\). It is clear that \(X\) is not a total monophonic set of \(G\).
If \(n=3\) and \(X\subseteq V_2\), then it is clear that \(X\) is a monophonic set of \(G\) and the subgraph induced by \(X\) has isolated vertices. Hence \(X\) is not a total monophonic set of \(G\). If \(n\geq 4\) and \(X\subseteq V_2\). Since \(X\) contains three elements from \(V_{2}\), there exists an element \(v\in V_2\) and \(v\notin X\). Since the vertex \(v\) is not an internal vertex of any \(r-s\) monophonic path, for some elements \(r\) and \(s\) in \(X\), \(X\) is not a monophonic set of \(G\). Therefore, we may take that \(X\cap V_1=\{x_l\}\) and \(X\cap V_2=\{y_i,y_j\}\). It is clear that \(X\) is not a total monophonic set of \(G\). Thus \(X\) is not a total monophonic set of \(G\). ◻
Theorem 2.20. Let \(G\) be a connected graph of order \(p\geq 3\). If \(G=\overline{K_2}+H\) where \(H\) is a graph of order \(p-2\) and \(\overline{K_2}\) is the complement of \(K_2\), then \(m_t(G)=3\).
Proof. If \(G = \overline{K_2}+H\), where \(H\) is a graph of order \(p-2\). Let \(S=V(\overline{K_2}) = \{u,v\}\). It is clear that \(S\) is a monophonic set of \(G\). Since the subgraph induced by \(S\) has isolated vertices \(u\) and \(v\), \(S\) is not a total monophonic set of \(G\). Also, it can be easily verified that any 2-element subset of \(V(G)\) is not a total monophonic set of \(G\). Then, for any \(x\in V(H)\), \(S\cup\{x\}\) is a total monophonic set of \(G\) and so \(m_t(G)=3\). ◻
Theorem 3.1. For positive integers \(a, b\) such that \(3 \leq a \leq b\) with \(b \leq 2a\), there exists a connected graph \(G\) such that \(m(G) = a\) and \(m_t(G) = b\).
Proof. We prove this theorem by considering two cases.
Case 1. \(3\leq a = b\). By Theorem 1.3 and Corollary 2.4, the complete graph \(K_a\) has the desired properties.
Case 2. \(3\leq a < b\). Let \(b = a+k\), where \(1 \leq k \leq a\). For \(k= 1\), the star \(K_{1, a}\) has the desired properties. Now, let \(k \geq 2\). Let \(C_i : v_{i,1}, v_{i,2},v_{i,3}, v_{i,4},v_{i,1}\,(1 \leq i \leq k-1)\) be \((k-1)\) copies of \(C_4\). Let \(H\) be the graph formed by identifying the vertices \(v_{i,4}\) of \(C_i\,(1 \leq i \leq k-1)\), say \(x\) the identified vertex and also joining the vertices \(v_{i,1}\) and \(v_{i,3}\,(1\leq i\leq k-1)\). Let \(G\) be the graph obtained from \(H\) by adding the \(a-k+1\) new vertices \(u_1, u_2, \ldots, u_{a-k+1}\) and joining each \(u_i(1\leq i\leq a-k+1)\) with \(x\). The graph \(G\) is shown in Figure 3. Let \(S = \{u_1, u_2, \ldots, u_{a-k+1},v_{1,2},v_{2,2},\cdots,v_{k-1,2}\}\) be the set of all extreme vertices of \(G\). By Theorem 1.1, every monophonic set of \(G\) contains \(S\). It is clear that \(S\) is the unique minimum monophonic set of \(G\) and \(m(G)=a\). Since \(S_1=S\cup\{x\}\) is the set of all extreme vertices and support vertex of \(G\), by Theorem 2.3, every total monophonic set of \(G\) contains \(S_1\). Since \(S_1\) is a monophonic set of \(G\) and the subgraph induced by \(S_1\) has the isolated vertices \(v_{1,2},v_{2,2},\cdots,v_{k-1,2}\), \(S_1\) is not a total monophonic set of \(G\). Note that any set \(S'\) of \(G\) with cardinality atmost \(b-1\) is not a total monophonic set of \(G\). Clearly, \(S_1\cup\{v_{1,1},v_{2,1},\cdots,v_{k-1,1}\}\) is a minimum total monophonic set of \(G\) and so \(m_t(G)=a+k=b\). ◻
In view of Theorem 2.13, we have the following realisation result.
Theorem 3.2. If \(p, a, b\) are positive integers such that \(4 \leq a \leq b \leq p\), then there exists a connected graph \(G\) of order \(p\) with \(m_t(G) = a\) and \(m_c(G) = b\).
Proof.We prove this theorem by considering four cases.
\(4\leq a = b = p\). Let \(G = K_p\). Then by Corollary 2.4 and Theorem 1.5, we have \(m_t(G) = m_c(G) = p\).
\(4\leq a < b = p\). Let \(P_{b-a+3} : u_1, u_2, \ldots, u_{b-a+3}\) be a path of order \(b-a+3\). Add \(a-3\) new vertices \(v_1, v_2, \ldots, v_{a-3}\) to \(P_{b-a+3}\) and join each \(v_i (1 \leq i \leq a-3)\) with \(u_{b-a+3}\), thereby producing the graph \(G\) in Figure 4 of order \(b = p\). Let \(S = \{u_1, v_1, v_2, \ldots, v_{a-3}, u_2, u_{b-a+3}\}\) be the set of all extreme vertices and support vertices of \(G\). By Theorem 2.3, every total monophonic set of \(G\) contains \(S\). It is clear that \(S\) is the unique minimum total monophonic set of \(G\) and so \(m_t(G) = a\).
Note that \(V(G)\) is the set of all extreme vertices and cut-vertices of \(G\). Then by Theorems 1.1 and 1.4, \(V(G)\) is the unique minimum connected monophonic set of \(G\) and so \(m_c(G) = b = p\).
\(4\leq a = b < p\). The graph \(G\) is obtained from the cycle \(C_{p-a+3}:v_1, v_2,\cdots,v_{p-a+3},v_1\) of length \(p-a+3\) by adding \(a-3\) new vertices \(u_1,u_2,\cdots, u_{a-3}\) and joining each \(u_i(1\leq i\leq a-3)\) to the vertex \(v_1\) of \(C_{p-a+3}\). The graph \(G\) of order \(p\) is shown in Figure 5. Let \(S=\{u_1,u_2,\cdots, u_{a-3}\}\) be the set of all extreme vertices and \(S'=S\cup\{v_1\}\) be the set of all extreme vertices and cutvertices of \(G\). Since \(v_1\) is the unique support vertex of any vertex in \(S\), by Theorem 2.3, \(S'\) is a subset of any total monophonic set of \(G\) and so \(m_t(G)\geq |S'|=a-2\). Since no vertex in \(C_{p-a+3}\) other than \(v_1\) does not lie on any monophonic path joining any two vertices in \(S'\), \(S'\) is not a total monophonic set of \(G\). Hence \(m_t(G)\geq a-1\). Let \(S''=S'\cup\{x\}\), where \(x\in V(C_{p-a+3})-\{v_1\}\). If \(x=v_2\) or \(x=v_{p-a+3}\), then the vertex \(v_i(3\leq i\leq p-a+2)\) does not lie any monophonic path joining any two vertices in \(S''\). If \(x=v_i(3\leq i\leq p-a+2)\), then its supporting vertices \(v_{i-1}\) and \(v_{i+1}\) do not lie on \(S''\). Hence \(S''\) is not a total monophonic set of \(G\) and so \(m_t(G)\geq |S''|=a-1\). Let \(S'''=S'\cup\{v_2,v_{p-a+3}\}\). It is clear that every vertex of \(G\) lies on a monophonic path joining any two vertices in \(S'''\) and no vertex in \(S'''\) is isolated, \(S'''\) is a total monophonic set of \(G\). Hence \(m_t(G)=a\). In a similar way we can easily verify that \(S'''\) is a minimum connected monophonic set of \(G\) and so \(m_c(G)=a\).
\(4\leq a <b < p\). Let \(H\) be the graph obtained from the path \(P_{b-a+3} : u_1, u_2, \ldots, u_{b-a+3}\) of order \(b-a+3\) by adding \(a-3\) new vertices \(v_1,v_2,\cdots,v_{a-3}\) and joining each \(v_i(1\leq i\leq a-3)\) to the vertex \(u_1\) of \(P_{b-a+3}\). If \(p-b=1\), the graph \(G\) is obtained from \(H\) by adding a new vertex \(u\) and joining the vertex \(u\) to the both the vertices \(u_1\), \(u_3\) of \(H\). The graph \(G\) is of order \(p\). Let \(S=\{v_1,v_2,\cdots, v_{a-3},u_{b-a+3},u_{b-a+2},u_1\}\) be the set of all extreme vertices of \(G\) and support vertices of \(G\). By Theorem 2.3, every total monophonic set of \(G\) contains \(S\). It is clear that \(S\) is the unique minimum total monophonic set of \(G\) and \(m_t(G)=a\). Let \(S_1 = \{v_1, v_2, \ldots, v_{a-3},u_{b-a+3}, u_1,u_3, u_4, \ldots, u_{b-a+2}\}\) be the set of all extreme vertices and cut-vertices of \(G\). By Theorems 1.1 and 1.4, every connected monophonic set of \(G\) contains \(S_1\). Since \(S_1\) is a monophonic set of \(G\) and the subgraph induced by \(S_1\) is not connected, \(S_1\) is not a connected monophonic set of \(G\). For any \(x\in V-S_1\), \(S_1\cup\{x\}\) is a minimum connected monophonic set of \(G\) and so \(m_c(G)=b\).
If \(p-b\geq 2\), the graph \(G\) is obtained from \(H\) and the path \(P_{p-b}:w_1,w_2,\cdots,w_{p-b}\) by joining the vertex \(w_1\) of \(P_{p-b}\) to the vertex \(u_1\) of \(P_{b-a+3}\); and joining the vertex \(w_{p-b}\) of \(P_{p-b}\) to the vertex \(u_3\) of \(P_{b-a+3}\). The graph \(G\) of order \(p\) is shown in Figure 6. Let \(S=\{v_1,v_2,\cdots, v_{a-3},u_{b-a+3}\}\) be the set of all extreme vertices and let \(S_1=\{u_1,u_3,\ldots,u_{b-a+2}\}\) be the set of all cut-vertices of \(G\). Since \(u_1\) is the unique support vertex any vertex in \(S\) and \(u_{b-a+2}\) is the unique support vertex of \(u_{b-a+3}\) in \(G\), by Theorem 2.3, \(S'=S\cup\{u_1,u_{b-a+2}\}\) is a subset of every total monophonic set of \(G\). It is clear that every vertex of \(G\) lies on a monophonic path joining any two vertices in \(S'\) and no vertex of \(S'\) is an isolated vertex. Hence \(S'\) is a minimum total monophonic set of \(G\) and so \(m_t(G)=|S'|=a\).
Also, by Theorems 1.1 and 1.4, every connected monophonic set of \(G\) contain \(S\cup S_1\). It is clear that every vertex of \(G\) lies on a monophonic path joining any two vertices in \(S\cup S_1\). Since the subgraph induced by \(S\cup S_1\) is not connected, \(S\cup S_1\) is not a connected monophonic set of \(G\). Hence \(m_c(G)> |S\cup S_1|=b-1\). Let \(S_2=S\cup S_1\cup\{u_2\}\). Then \(S_2\) is a monophonic set of \(G\) and the subgraph induced by \(S_2\) is connected. Hence \(S_2\) is a minimum connected monophonic set of \(G\) and \(m_c(G)=b\). ◻
Theorem 3.3. If \(p,d\) and \(k\) are positive integers such that \(2\leq d\leq p-2\), \(k\geq 4\) and \(p-d-k+2\geq 0\), then there exists a connected graph G of order p with monophonic diameter \(d\) and \(m_{t}(G)=k\).
Proof. We prove this theorem by considering two cases.
\(d=2\). Let G be the graph obtained from the path \(P_3:x, y, z\) of order 3 by adding \(p-3\) new vertices \(v_1, v_2,\ldots , v_{p-k}, w_1, w_2,\ldots,w_{k-3}\) and joining each \(w_i(1 \leq i \leq k- 3)\) to y; joining each \(v_i (1 \leq i \leq p -k)\) with x, y and z; and joining each \(v_i(1 \leq i\leq p- k- 1)\) with \(v_j (i + 1 \leq j \leq p- k)\). The graph G of order \(p\) is shown in Figure 7.
It is clear that for any vertex \(u\in V(G),\,1\leq e_m(u)\leq 2\), and \(e_m(w_i)=2\,(1\leq i\leq k-3)\), the monophonic diameter of \(G\) is 2. Let \(S = \{w_1,w_2,w_3, \ldots ,w_{k-3}, x, z,y\}\) be the set of all extreme vertices and support vertex of G. By Theorem 2.3, every total monophonic set of G contains S. It is easily verified that S is the unique minimum total monophonic set of G and so \(m_{t}(G)=k\).
Case 2. \(d\geq 3\). Let \(G\) be the graph obtained from the cycle \(C_{d+1}:v_1,v_2,\cdots, v_{d+1},v_1\) of order \(d+1\) by adding \(p-d-1\) new vertices \(w_1,w_2,\cdots,w_{p-d-k+2},u_1, u_2,\cdots,u_{k-3}\) and joining each \(w_i(1\leq i\leq p-d-k+2)\) to the vertices \(v_1\) and \(v_3\); and joining each \(u_i(1\leq i\leq k-3)\) to the vertex \(v_1\). The graph \(G\) of order \(p\) is shown in Figure 8.
It is clear that \(e_m(u_i)=e_m(v_3)=e_m(v_d)=d\,(1\leq i\leq k-3)\) and for any other vertex \(u,\,e_m(u)=d-1\) so that the monophonic diameter of \(G\) is \(d\). Let \(S=\{u_1,u_2,\ldots, u_{k-3}\}\) be the set of all extreme vertices of \(G\). Since \(v_1\) is the unique support vertex of every vertex in \(S\), by Theorem 2.3, \(S'=S\cup\{v_{1}\}\) is subset of any total monophonic set of \(G\) and so \(m_t(G)\geq |S'|=k-2\). Since no vertex in \(V(G)-S'\) does not lie on any monophonic path joining any two vertices in \(S'\), \(S'\) is not a total monophonic set of \(G\). Hence \(m_t(G)\geq k-1\). Let \(S''=S'\cup\{x\}\), where \(x\in V(G)-S'\). If \(x\in \{v_2,v_{d+1},w_1,w_2,\ldots,w_{p-d-k+2}\}\), then the vertex \(x\) does not lie on any monophonic path joining any two vertices in \(S''\). If \(x=v_i(3\leq i\leq d)\) then no one of its supporting vertices does not lie on any monophonic path joining any two vertices in \(S''\). Hence \(S''\) is not a total monophonic set of \(G\) and so \(m_t(G)>|S''|=k-1\). Let \(S'''=S'\cup\{v_2,v_{d+1}\}\). It is clear that every vertex of \(G\) lies on a monophonic path joining any two vertices in \(S'''\) and no vertex of \(S'''\) is an isolated vertex. Hence \(S'''\) is a minimum total monophonic set of \(G\) and so \(m_t(G)=|S'''|=k\). ◻