Menu
A path \(x_1, x_2, \dots, x_n\) in a connected graph \( G \) that has no edge \( x_i x_j \) \((j \geq i+3)\) is called a monophonic-triangular path or mt-path. A non-empty subset \( M \) of \( V(G) \) is a monophonic-triangular set or mt-set of \( G \) if every member in \( V(G) \) exists in a mt-path joining some pair of members in \( M \). The monophonic-triangular number or mt-number is the lowest cardinality of an mt-set of \( G \) and it is symbolized by \( mt(G) \). The general properties satisfied by mt-sets are discussed. Also, we establish \( mt \)-number boundaries and discover similar results for a few common graphs. Graphs \( G \) of order \( p \) with \( mt(G) = p \), \( p – 1 \), or \( p – 2 \) are characterized.
In this paper, a graph \(G=(V,E)\) refers to a finite undirected connected graph that lacks loops and multiple edges. The order and size of a graph are represented by \(p\) and \(q\), respectively. For basic definitions and terminologies, we refer to [1-3]. A vertex \(v\) of a graph \(G\) is said to be simplicial or extreme if the subgraph induced by its neighbors in complete. If the degree of a vertex \(v\) is one, then \(v\) is called an end-vertex.
In graph theory, there are many types of paths of interest joining any two vertices in a graph. The important paths joining any two vertices in a graph are geodesic path (a shortest path), detour path (a longest path), monophonic path (a chordless path), detour monophonic path (a longest chordless path) and triangle free detour path (a longest path having no triangle). In the year 2021, Santhakumaran and Titus [4] introduced a new path named as monophonic-triangular path or \(mt\)-path by not allowing a cycle of order more than 3 (i.e., a triangle) in it. Hence, if an edge \(e\) of a monophonic path \(P\) is an edge of a triangle in \(G\), then we enlarge the path \(P\) by replacing the edge \(e\) by the remaining two edges of the triangle. Let \(Q\) be the revised path. Then the paths \(P\) and \(Q\) are known as monophonic-triangular path or \(mt\)-path. Clearly, the monophonic-triangular path covers more number of vertices than the usual monophonic path. Therefore, the monophonic-triangular path is a more powerful tool for covering the vertices of a graph.
The distance \(d(a,b)\) between the vertices \(a\) and \(b\) in a graph \(G\) is the length of one of the shortest \(a-b\) paths in \(G\). An \(a-b\) \(geodesic\) is an \(a-b\) path with length \(d(a,b)\). A non-empty subset \(S\) of \(V(G)\) is a geodetic set of \(G\) if every member in \(V(G)\) lies on a geodesic path joining some pair of members in \(S\). The geodetic number is the smallest cardinality of a geodetic set of \(G\) and it is denoted by \(g(G)\). The geodetic number of a graph was introduced in [5] and further investigated in [6-8].
The detour distance \(D(a,b)\) between the vertices \(a\) and \(b\) in a graph \(G\) is the length of one of the longest \(a-b\) paths in \(G\). In [9], the detour distance was first introduced. An \(a-b\) detour is an \(a-b\) path with length \(D(a,b)\). A non-empty subset \(S\) of \(V(G)\) is a detour set of \(G\) if every member in \(V(G)\) lies on a detour path joining some pair of members in \(S\). The detour number of a graph is the smallest cardinality of a detour set of \(G\) and it is denoted by \(dn(G)\). The detour number of a graph was introduced in [10] and expanded upon in [11,12].
An \(a-b\) path \(P\) is said to be an \(a-b\) monophonic path in \(G\) if \(P\) has no chords. The monophonic distance \(d_m(a,b)\) between the vertices \(a\) and \(b\) in a graph \(G\) is the length of one of the longest \(a-b\) monophonic paths in \(G\). The monophonic distance was introduced by Santhakumaran and Titus in [13] and further studied in [14]. A non-empty subset \(S\) of \(V(G)\) is a monophonic set of \(G\) if every member in \(V(G)\) lies on a monophonic path joining some pair of members in \(S\). The monophonic number is the smallest cardinality of a monophonic set of \(G\) and it is denoted by \(m(G)\). The concept of monophonic number was studied in [15-17].
An \(a-b\) detour monophonic path is one of the longest \(a-b\) monophonic paths. A non-empty subset \(S\) of \(V(G)\) is a detour monophonic set of \(G\) if every member in \(V(G)\) lies on a joining some pair of members in \(S\). The detour monophonic number is the lowest cardinality of a detour monophonic set of \(G\) and it is symbolized by \(dm(G)\). The idea of detour monophonic number of a graph was presented in [18], which was expanded upon in [19].
An \(a-b\) path \(P\) is said to be an \(a-b\) triangle free path in \(G\) if no three vertices of \(P\) produce a cycle \(C_3\) in \(G\). The triangle free detour distance \(D_{\triangle f}(a,b)\) between the vertices \(a\) and \(b\) in a graph \(G\) is the length of one of the longest \(a-b\) triangle free path in \(G\). An \(a-b\) triangular free detour is an \(a-b\) triangle free path with length \(D_{\triangle f}(a,b)\). The concept was studied in [20] and further studied in [21]. A non-empty subset \(S\) of \(V(G)\) is a triangle free detour set of \(G\) if every member in \(V(G)\) exists in a triangle free path joining some pair of members in \(S\). The triangle free detour number is the lowest cardinality of a triangle free detour set of \(G\) and it is symbolized by \(dn_{\triangle f}(G)\).
A path \(x_1,x_2,\dots,x_n\) in a connected graph \(G\) with no edge \(x_ix_j\) \((j \ge i+3)\) is called a monophonic-triangular path or mt-path. The monophonic-triangular distance or mt-distance \(d_{mt}(a,b)\) from \(a\) to \(b\) is defined as the length of one of the longest \(a-b\) mt-paths in \(G\). The mt-eccentricity \(e_{mt}(v)\) of a vertex \(v\) in \(G\) is defined as the maximum mt-distance between \(v\) and other vertices in \(G\). The mt-radius \(rad_{mt}(G)\) is defined as the minimum mt-eccentricity among the vertices of \(G\) and the mt-diameter \(diam_{mt}(G)\) is defined as the maximum mt-eccentricity among the vertices of \(G\). The concept of monophonic-triangular distance in graphs introduced in [4]. This new distance motivates us to introduce a new parameter “monophonic-triangular number”.
The following theorems are used in the sequel.
Theorem 1. [4] Let \(G\) be a connected graph of order \(p\ge 2\). Then \(diam_{mt}(G)=1\) if and only if \(G=K_2\).
Theorem 2. [16] Every extreme vertex of a connected graph \(G\) belongs to every monophonic set of G.
Theorem 3. [16] Let \(G\) be a connected graph of order \(p\ge 3\). Then \(m(G)=p-1\) if and only if \(G=K_1+\cup m_jK_j\), where \(\sum m_j \ge 2\).
Theorem 4. [5] Each extreme vertex of a connected graph \(G\) belongs to every geodetic set of \(G\).
Definition 1. A non-empty subset \(M\) of \(V(G)\) is a monophonic-triangular set or mt-set of \(G\) if every member in \(V(G)\) exists in an mt-path joining some pair of members in \(M\). The monophonic-triangular number or mt-number is the smallest cardinality of an mt-set of \(G\) and it is symbolized by \(mt(G)\).
Example 1.
(i) For the graph \(G\) given in Figure 1, \(M_1\) = \(\{u,x\}\) and \(M_2 = \{z,x\}\) are the minimum mt-sets of \(G\). Hence \(mt(G)=2\).
(ii) Consider the graph \(G\) given in Figure 2. It can be easily verified that \(M_1=\{a_1,a_3,a_5,b_2,\\ b_3, c_2,c_4,d_1,d_2\}\) is a minimum geodetic set, \(M_2=\{a_1,b_1,c_1,d_1\}\) is a minimum detour set, \(M_3=\{a_1,a_5,b_2,c_2,c_4,d_1,d_2\}\) is a minimum monophonic set, \(M_4=\{a_1,a_5,b_2,b_3,c_2,c_4,d_1,d_2\}\) is a minimum detour monophonic set, \(M_5=\{a_1,a_5,b_1,c_1,d_1,d_2\}\) is a minimum triangle free detour set and \(M_6=\{a_3,b_2,c_2,c_4,d_1\}\) is a minimum \(mt\)-set of \(G\) and so \(d(G)=9\), \(D(G)=4\), \(m(G)=7\), \(dm(G)=8\), \(dn{_\triangle f}(G)=6\) and \(mt(G)=5\). Hence the parameters based on the paths geodesic, detour, monophonic, detour monophonic, triangle free detour and monophonic-triangular are different.
Theorem 5.
(i) Each end-vertex of \(G\) is a member of every \(mt\)-set of \(G.\)
(ii) No cut-vertex of \(G\) is a member of any minimum \(mt\)-set of \(G\).
Proof.
(i) Let \(v\) be an end-vertex of \(G\). Then \(v\) is either the initial vertex or the terminal vertex of any monophonic-triangular path containing the vertex \(v\). Hence \(v\) is not an internal vertex of any monophonic-triangular path so that \(v\) is a member of every mt-set of \(G\).
(ii) Suppose \(v\) is a cut-vertex of \(G\) and let \(M\) be a minimum mt-set of \(G\) that contains \(v\). Now, claim that each component of \(G-v\) contains an element of \(M\). If not, then there is a component \(B\) of \(G-v\) such that \(B\) contains no element of \(M\). Let \(u\) be any vertex in \(B\). Since \(M\) is an mt-set, there exist two vertices \(x\) and \(y\) in \(M\) such that \(v\) exists in some \(x-y\) monophonic-triangular path, say \(P\). Then \(u\ne x,y\). Since \(v\) is a cut-vertex of \(G\), the \(x-u\) subpath \(P_1\) of \(P\) and the \(u-y\) subpath \(P_2\) of \(P\) both contain \(v\), it results that \(P\) is not a path, it contradicts our assumption. Thus each component of \(G-v\) contains an element of \(M\). Let \(V_1\) and \(V_2\) be two different components of \(G-v\) and let \(u \in V_1\) and \(w \in V_2\). Then \(v\) is an internal vertex of an \(u-w\) monophonic-triangular path in \(G\). Let \(M'= M-\{v\}\). Then each vertex that lies on an \(u-v\) monophonic-triangular path also exists on an \(u-w\) monophonic-triangular path and hence \(M'\) is an mt-set of \(G\), it contradicts to \(M\) a minimum mt-set of \(G\).
◻
Corollary 1. If \(G\) is a tree graph with some \(k\) end-vertices, then \(mt(G)\) = \(k\).
Corollary 2. If a graph \(G\) with \(k\geq2\) end-blocks, then \(mt(G)\) \(\geq\) \(k\).
Corollary 3. In a graph \(G\), if \(k\) is the largest number of blocks to which a vertex in \(G\) belongs, then \(mt(G)\) \(\geq\) \(k\).
Theorem 6.
For the graph \(K_p\) \((p\geq 2)\), \(\textit{mt}(K_p)=2\).
For the graph \(C_p\) \((p\geq 3)\), \(\textit{mt}(C_p)=2\).
For the graph \(W_p = K_1+ C_{p-1}\) \((p\geq 5)\), \(\textit{mt}(W_p)=2\).
For the graph \(K_{m,n}\) \((m,n\geq 2)\), \(\textit{mt}(K_{m,n})=min\{4,m,n\}\).
Proof.
For any two vertices \(x\) and \(y\) in \(K_p\), any vertex \(v\ne x,y\) is a member on the \(x,v,y\) monophonic-triangular path. Hence \(M=\{x,y\}\) is an \(\textit{mt}\)-set of \(K_p\) and so \(\textit{mt}(K_p)=2\).
For any two non-adjacent vertices \(x\) and \(y\) in \(C_p\), every vertex of \(C_p\) exists on an \(x-y\) monophonic-triangular path. Hence \(M=\{x,y\}\) is an \(\textit{mt}\)-set of \(C_p\) and so \(\textit{mt}(C_p)=2\).
Let \(M=\{x,y\}\), where \(x\) and \(y\) are any two non-adjacent vertices in \(W_p\). It is obvious that each vertex of \(W_p\) exists on an \(x-y\) monophonic-triangular path. Then \(M\) is an \(\textit{mt}\)-set of \(W_p\) and so \(\textit{mt}(W_p)=2\).
Let the partite sets of \(K_{m,n}\) \((2 \le m \le n)\) be \(V_1\) = \(\{x_1,x_2,\dots,x_m\}\) and \(V_2\) = \(\{y_1,y_2,\dots,y_n\}\). When \(m=2\) or \(3\), \(M=V_1\) is a minimum mt-set of \(K_{m,n}\) and so \(\textit{mt}(K_{m,n})=\left|M\right|=m\). When \(m\ge4\), Let \(M=\{x_1,x_2,y_1,y_2\}\). It is evident that every vertex in \(V_1\) is a member on a \(y_1-y_2\) monophonic-triangular path and every vertex in \(V_2\) is a member on an \(x_1-x_2\) monophonic-triangular path. As a result, \(M\) is an mt-set of \(K_{m,n}\) and hence \(mt(K_{m,n})\le \left|M\right|=4\). It is evident that neither two members nor three members subset of \(V(K_{m,n})\) will form an mt-set of \(K_{m,n}\), we have \(mt(K_{m,n})=4\).
◻
Proposition 1. If \(G\) is any connected graph, then \(2\le mt(G)\le m(G) \le p\).
Proof. To form an mt-set, we need minimum two vertices and so \(mt(G)\ge2\). Since every monophonic set is a monophonic-triangular set, \(mt(G)\le m(G)\). Also, since \(V(G)\) is a monophonic set, we have \(m(G)\le p\). Thus \(2\le mt(G)\le m(G) \le p\). ◻
Remark 1. For the cycle \(C_p\), \(mt(C_p)=2\) and for the complete graph \(K_2\), \(mt(K_2)=2=p\). Therefore the bounds for \(mt(G)\) in Proposition 1 are sharp.
We provide a better upper bound for the mt-number of a graph in the subsequent theorem.
Theorem 7. For any connected graph \(G\) with \(p\) vertices, \(mt(G)\le p-diam_{mt}(G)+1\).
Proof. Let \(P:a=a_0, a_1, \dots, a_d=b\) be an \(a-b\) \(mt\)-path of length \(d=diam_{mt}(G)\). Then \(S=V(G)-\{a_1, a_2, \dots, a_{d-1}\}\) is an \(mt\)-set of \(G\) and so \(mt(G)\le |S|=p-d+1\). Hence \(mt(G) \le p -diam_{mt}(G)+1\). ◻
Remark 2. In \(K_3\), \(diam_{mt}(K_3)=2\) and \(mt(K_3)=2=p – diam_{mt}(K_3)+1\). Therefore the bound in Theorem 7 is sharp. The inequality in Theorem 7 can also be strict. For the cycle \(C_p\) \((p\ge4)\), \(diam_{mt}(C_p)=p-2\) and \(mt(C_p)=2\). Thus \(mt(C_p)<p-diam_{mt}(C_p)+1\). Also, since \(diam_m(G) \le diam_{mt}(G)\), we have \(mt(G) \le p-diam_m(G)+1\).
Theorem 8. Let \(G\) be a graph with order \(p\ge2\). Then \(G=K_2\) if and only if \(mt(G)=p\).
Proof. Supposing that \(G=K_2\), subsequently \(mt(G)=2=p\). Conversely, let \(mt(G)=p\). If \(G\ne K_2\), then \(G\) contains minimum 3 vertices. Since \(G\) is connected with at least 3 vertices, \(diam_{mt}(G) \ge 2\). Then by Theorem 7, \(mt(G) \le p-diam_{mt}(G)+1 \le p-1\), it contradicts our assumption. Hence \(G=K_2\). ◻
Theorem 9. Let \(G\) be a graph with order \(p\ge3\). Then \(G\) is either \(K_3\) or \(K_{1,p-1}\) if and only if \(mt(G)=p-1\).
Proof. Supposing that \(G=K_3\) or \(K_{1,p-1}\), subsequently by Theorem 6(i) and Corollary 1, \(mt(G)=p-1\). Conversely, suppose that \(mt(G)=p-1\). Then by Proposition 1, we have \(m(G)=p-1\) or \(p\). If \(m(G)=p\), then \(G=K_p\) and so by Theorem 6 (i), \(mt(G)=2=p-1\) only for \(p=3\). Hence \(G=K_3\). If \(m(G)=p-1\), then by Theorem 3, \(G=K_1+ \cup m_j K_j\), where \(\sum m_j\ge 2\). Now, we claim that \(G\) is a star. i.e., \(j=1\). If not, then \(G\) has at least one clique \(K_j\) of order more than one. Let \(S\) be a collection of exactly one vertex from each clique of \(G=K_1+ \cup m_j K_j\). Clearly, \(S\) is an \(mt\)-set of \(G\) and so \(mt(G) \le |S|\le p-2\), it contradicts our assumption. Hence \(G\) is a star. ◻
Theorem 10.
Let \(G\) be a graph with order \(p\ge 5\). Then \(G\) is either a double star or \(K_{1,p-1}+e\) if and only if \(mt(G)=p-2\).
Proof. If \(G\) is a double star, then by Corollary 1, \(mt(G)=p-2\). If \(G=K_{1,p-1}+e\), then \(G\) contains exactly one cut-vertex, say \(x\); two simplicial vertices of degree two, say \(y_1\) and \(y_2\); and \(p-3\) end-vertices. Let \(M\) be the end-vertices set of \(G\). By Theorem 5(i), every member of \(M\) is included in each mt-set of \(G\). Let \(M'=M\cup \{y_1\}\). As a result, a minimum mt-set of \(G\) is \(M'\) and hence \(mt(G)=p-2\).
Conversely, let \(G\) be a graph
of order \(p\ge5\) such that \(mt(G)=p-2\). Then by Theorem 1, \(diam_{mt}(G) \ge 2\). If \(diam_{mt}(G)\ge 4\), then by Theorem 7,
\(mt(G)\le p-3\), it contradicts our
assumption. Hence \(diam_{mt}(G)=2\) or
\(3\). If \(G\) is a tree, then \(G\) is either a star or a double star. If
\(G\) is a star, then by Corollary 1, \(mt(G)=p-1\), it contradicts our assumption.
If \(G\) is a double star, then by
Corollary 1, \(mt(G)=p-2\). Now, let \(G\) be not a tree. Let \(k\) denote the length of the longest cycle
with no inner chords in \(G\). Since
\(diam_{mt}(G)=2\) or \(3\), we have \(k\le 5\). Now we have three cases.
Case 1. \(k=5\). Let
5-cycle in \(G\) be \(C_5\) = \(v_1,v_2,v_3,v_4,v_5,v_1\).
Then mt-set of \(G\) is
\(M=(V(G)-V(C_5)) \cup \{v_1,v_3\}\)
and hence \(mt(G)\le p-3\), it
contradicts our assumption.
Case 2. \(k=4\).
Let 4-cycle in \(G\) be \(C_4=v_1,v_2,v_3,v_4,v_1\). Since \(p\ge5\) and \(G\) is connected, there exists a vertex,
say \(u\), not on \(C_4\) such that \(u\) is adjacent to some vertices in \(C_4\). If \(u\) is adjacent to exactly one vertex, say
\(v_1\), then an mt-set of
\(G\) is \(M=V(G)-\{v_1,v_2,v_4\}\) and hence \(mt(G)\le p-3\), it contradicts our
assumption. If \(u\) is adjacent to two
consecutive vertices of \(C_4\), say
\(v_1\) and \(v_2\), then also \(M\) is an \(mt\)-set of \(G\) and so \(mt(G)=p-3\), it contradicts our assumption.
If \(u\) is adjacent to two
non-consecutive vertices of \(C_4\),
say \(v_1\) and \(v_3\), then \(M_1=V(G)-\{u, v_2, v_4\}\) is an \(mt\)-set of \(G\) and so \(mt(G)=p-3\), it contradicts our
assumption.
Case 3. \(k=3\).
If \(G\) contains 2 or more edge distinct triangles, then \(diam_{mt}(G)\ge 4\). Then by Theorem 7, \(mt(G)\le p-3\), it contradicts our assumption. If \(G\) contains two common edge triangles, then \(G_1\) or \(G_2\) in Figure 3 is a subgraph of \(G\). As a result, mt-set of \(G\) is \(M=V(G)-\{x_1,x_2,x_3\}\) and hence \(mt(G)\le p-3\), it contradicts our assumption. If \(G\) contains three or more common edge triangles, then \(G_3\) in Figure 3 is a subgraph of \(G\). As a result, mt-set of \(G\) is \(M=V(G)-\{x_1,x_2,x_3\}\) and hence \(mt(G)\le p-3\), it contradicts our assumption. Hence \(G\) contains a unique triangle \(C_3=v_1,v_2,v_3,v_1\). If there are two or three vertices of \(C_3\) having degree 3 or more, then \(diam_{mt}(G)\ge4\), it contradicts our assumption. Thus exactly one vertex in \(C_3\) has degree 3 or more. Since \(diam_{mt}(G)=3\), it follows that \(G=K_{1,p-1}+e\).
Remark 3. Let \(G\) be a graph with order \(p\le 4\). Then \(mt(G)=p-2\) if and only if \(G\) is any connected graph of order four other than a star.
Theorem 11. If \(G\) is any connected graph of order \(p\), then \(2\leq mt(G)\leq m(G) \leq g(G)\leq p\).
Proof. Obviously, every monophonic path is an mt-path and every geodesic is a monophonic path. Hence every monophonic set is an mt-set and every geodetic set is a monophonic set, and so \(mt(G)\leq m(G) \leq g(G)\). Then the result follows from Proposition 1. ◻
Theorem 12. For each triple (k, l, n) with \(2 \leq k \leq l\leq n\), there exists a connected graph \(G\) with \(mt(G)=k\), \(m(G)=l\) and \(g(G)=n\).
Proof. If \(2 \leq k = l = n\), then take \(G\) as a tree with number of end-vertices \(k\). Then by Theorems 2, 4 and Corollary 1, we have \(mt(G)=m(G)=g(G)=k\). In other cases, we construct a graph \(G\) as follows: Let \(P\) represent a path \(u_1, u_2, u_3, u_4\) of length 3 and \(P_i\) represent \(n-l\) copies of a path \(x_i, y_i\) \((1 \leq i \leq n-l)\) of length 1. Assume \(G\) is the graph formed by connecting each \(x_i\) \((1\le i \le n-l)\) to \(u_2\), connecting each \(y_i\) \((1\le i \le n-l)\) to \(u_4\), and adding \(l-1\) new vertices \(v_1, v_2,\dots,v_{k-1}, w_1, w_2,\dots,w_{l-k}\) and connecting each \(v_i\) \((1\le i \le k-1)\) to \(u_4\), and connecting each \(w_i\) \((i\le i \le l-k)\) to \(u_3\) and \(u_4\). The graph \(G\) is shown in Figure 4.
The set of simplicial vertices is \(M'= M\cup \{w_1,w_2,\dots,w_{l-k}\}\),
where \(M=\{u_1, v_1,
v_2,\dots,\)
\(v_{k-1}\}\) is the set of
end-vertices. By Theorem 5(i), every member of \(M\) is included in each \(mt\)-set of \(G\). As \(M\) is itself an \(mt\)-set, \(mt(G)=|M|= k\). Similarly, by Theorem 2, every
member of \(M'\) is included in
each monophonic set of \(G\).
Obviously, \(M'\) is a monophonic
set of \(G\) and hence \(m(G)=|M'|=l\). Now, by Theorem 4, every
member of \(M'\) is included in
each geodetic set of \(G\). Obviously,
the vertices \(x_i\) and \(y_i\) \((1 \le i
\le n-l)\) do not lie on any geodesic connecting any two vertices
in \(M'\). As a result, \(M'\) is not a geodetic set of \(G\) and hence \(g(G)>|M'|\). We can easily verify
that either \(x_i\) or \(y_i\) \((i \le i
\le n-l)\) must belong to every geodetic set of \(G\). Let \(M''= M' \cup \{x_1, x_2, \dots,
x_{n-l}\}\). Now, every vertex of \(G\) exists on a geodesic joining two
vertices in \(M''\). Hence
\(M''\) is a geodetic set of
\(G\) and so \(g(G)=|M''|=n\). In the next
theorem, we construct a graph of prescribed order, mt-diameter
and mt-number under suitable conditions. ◻
Theorem 13. For each triple (k, l, p) with \(2\le l \le p-k+1\) and \(k\ge 3\), there exists a connected graph \(G\) with \(diam_{mt}(G)=k\), \(mt(G)=l\) and \(|V(G)|=p\).
Proof.
Assume \(G\) is the graph formed
from the path \(P_k:u_1,u_2,\dots,u_k\)
of order \(k\) by adding \(p-k\) new vertices \(v_1,v_2,\dots,v_{p-k-l+2},w_1,w_2,\dots,w_{l-2}\)
and connecting each \(w_i\) \((1 \le i \le l-2)\) to \(u_2\), and joining each \(v_i\) \((1\le i
\le p-k-l+2)\) to both \(u_1\)
and \(u_2\). The graph \(G\) is shown in Figure 5 and the order of
the graph \(G\) is \(p\). Obviously, for any \(x \in V(G)\), \(2\le e_{mt}(x) \le k\) and for any \(y \in \{u_1, u_k, v_1,
v_2,\dots,v_{p-k-l+2}\}\), \(e_{mt}(y)=k\). Hence \(diam_{mt}(G)=k\). Now, we claim that \(mt(G)=l\). Let the end-vertices set of
\(G\) be \(M=\{w_1, w_2,\dots, w_{l-2}, u_k\}\). Then
by Theorem 5(i), every member of \(M\) is included in each mt-set of
\(G\) and hence \(mt(G)\ge|M|=l-1\). Obviously, the vertices
\(u_1, v_1, v_2, \dots, v_{p-k-l+2}\)
do not exist on any \(u-v\)
monophonic-triangular path for every \(u,v\in
M\). Let \(M'=M\cup\{u_1\}\). Since the vertices
\(u_1, v_1, v_2, \dots, v_{p-k-l+2}\)
lie on an \(u_{1}-y\)
monophonic-triangular path for some \(y\in
M\), a minimum mt-set of \(G\) is \(M'\) and hence \(mt(G)=|M'|=k\). Hence the
result. ◻
Ostrand [22] has shown that every two positive integers \(k\) and \(l\) with \(k\le l \le 2k\) are realisable as the radius and diameter of a graph, respectively, because \(rad(G)\le diam(G)\le 2\) \(rad(G)\). Santhakumaran et al.[16] have shown that every two positive integers \(k\) and \(l\) with \(k\le l\) are realisable as the monophonic radius and monophonic diameter of a connected graph, respectively, because \(rad_m(G)\le diam_m(G)\). Similarly, since \(rad_{mt}(G)\le diam_{mt}(G)\), it was demonstrated by Titus et.al.[4] that all positive integers \(k\) and \(l\) with \(k\le l\), are realisable as the mt-radius and mt-diameter of a connected graph, respectively. This theorem can also be extended so that the mt-number can be prescribed when \(rad_{mt}(G)<diam_{mt}(G)\).
Theorem 14. ] For any triple (k, l, n) with \(2\le k < l\) and \(n \ge3\), there is a connected graph \(G\) with \(rad_{mt}(G)=k\), \(diam_{mt}(G)=l\) and \(mt(G)=n\).
Proof. We consider three cases to prove this
theorem.
Case 1. \(k+2 \le l \le
2k\).
Let the cycles of order \(k+2\) and \(l-k+2\) be \(C_1: u_0, u_1, \dots, u_{k+1}, u_0\) and \(C_2: v_0, v_1, \dots, v_{l-k+1}, v_0\), respectively.
Assume \(H\) is the graph formed from \(C_1\) and \(C_2\) by (i) merging the vertices \(u_0\) of \(C_1\) and \(v_0\) of \(C_2\), (ii) connecting the vertices \(u_0\) and \(u_k\) of \(C_1\), and (iii) connecting the vertices \(v_0\) and \(v_{l-k}\) of \(C_2\). Assume \(G\) is the graph formed from \(H\) by adding \(n-2\) new vertices \(w_1, w_2,\dots , w_{n-2}\) and connecting each vertex \(w_i(1 \le i \le n-2)\) to the vertex \(v_0\) in \(H\). In Figure 6, the graph \(G\) is shown.
Obviously, the mt-eccentric vertex of \(u_0\) is \(u_2\), the mt-eccentric vertex of
\(u_2\) is \(v_2\), and so \(e_{mt}(u_0)=k\) and \(e_{mt}(u_2)=l\). Also, for any vertex \(x\) in \(G\), \(k \le
e_{mt}(x)\le l\). Hence \(rad_{mt}(G)=k\) and \(diam_{mt}(G)=l\). Let \(M=\{w_1, w_2, \dots, w_{n-2}\}\) be the
end-vertices set of \(G\). By Theorem
5(i),
every member of \(M\) is included in
any mt-set of \(G\) and hence
\(mt(G)\ge|M|=n-2\). Also, it is
evident that every mt-set of \(G\) contains at least one vertex from each
cycle \(C_1\) and \(C_2\). Hence \(mt(G)\ge n\). Let \(M'=M \cup \{u_2, v_2\}\). Clearly,
\(M'\) is an mt-set of
\(G\) and hence \(mt(G)=|M'|=n\).
Case 2. \(l=k+1\).
Assume \(G\) is a graph formed from a cycle \(C:u_0, u_1, \dots, u_{k+1}, u_0\) by connecting the vertices \(u_0\) and \(u_k\), and adding \(n-1\) new vertices \(v_1, v_2, \dots, v_{n-1}\) and connecting each vertex \(v_i(1 \le i \le n-2)\) to the vertex \(u_0\) of \(C\). In Figure 7, the graph \(G\) is shown.
Obviously, the mt-eccentric vertex of \(u_0\) is \(u_2\), the mt-eccentric vertex of
\(v_1\) is \(u_2\), and \(e_{mt}(x)\) is either \(k\) or \(k+1\) for any vertex \(x\) in \(G\). Hence \(rad_{mt}(G)=k\) and \(diam_{mt}(G)=k+1=l\). Let the end-vertices
set of \(G\) be \(M=\{v_1, v_2, \dots, v_{n-1}\}\). By
Theorem 5(i), every member of \(M\) is included in any mt-set of
\(G\) and hence \(mt(G) \ge |M| = n-1\). It is evident that
the vertices in \(V(C)-\{u_0\}\) do not
lie on any \(x-y\) mt-path in
\(G\) for any \(x,y \in M\). Hence \(M\) is not an mt-set of \(G\) and so \(mt(G)>|M|=n-1\). Let \(M'=M\cup \{u_2\}\). Clearly, \(M'\) is an mt-set of \(G\) and hence \(mt(G)=|M'|=n\).
Case 3. \(l>2k\).
Let \(W=K_1+C_{l+2}\) be a wheel with \(V(K_1)=\{x\}\) and \(V(C_{l+2})=\{v_1, v_2, \dots ,v_{l+2}\}\), and let \(C: u_0, u_1, \dots, u_{k+1}, u_0\) be a cycle of order \(k+1\). Assume \(G\) is the graph formed from the wheel \(W\) and the cycle \(C\) by merging the vertex \(x\) of \(W\) and \(u_0\) of \(C\), and by adding \(n-3\) new vertices \(w_1, w_2,\dots ,w_{n-3}\) and connecting each \(w_i\) \((1 \le i \le n-3)\) to the vertex \(x\) of \(W\). In Figure 8, the graph \(G\) is shown.
Obviously, \(u_k\) is an mt-eccentric vertex of \(x\), \(v_{l+2}\) is an mt-eccentric vertex of \(v_1\), and so \(e_{mt}(x)=k\) and \(e_{mt}(v_1)=l\). Also, for any vertex \(u\) in \(G\), \(k \le e_{mt}(u) \le l\). Hence \(rad_{mt}(G)=k\) and \(diam_{mt}(G)=l\). Let \(M=\{w_1, w_2, \dots, w_{n-3}\}\) be the end-vertices set of \(G\). By Theorem 5(i), every member of \(M\) is included in any mt-set of \(G\) and hence \(mt(G) \ge|M|=n-3\). It is clear that every mt-set of \(G\) contains at least one vertex from the cycle \(C\) and at least two vertices from the cycle \(C_{l+2}\) of the wheel \(W\). Hence \(mt(G)\ge n\). Let \(M'=M \cup \{u_k, v_1, v_{l+1}\}\). Clearly, \(M'\) is an mt-set of \(G\) and hence \(mt(G)=|M'|=n\). ◻
Problem 1. For any pair \((k,n)\) with \(k\ge 2\) and \(n\ge 2\), is there any connected graph \(G\) with \(rad_{mt}(G)=diam_{mt}(G)=k\) and \(mt(G)=n\)?
In this paper, we presented bounds and realization results for the mt-number of a connected graph. Additionally, we provided some characterization results for the parameter \(mt(G)\). These findings contribute to a deeper understanding of the parameter monophonic-triangular number.
Furthermore, to enhance the security and efficiency of networks, we aim to implement a routing protocol based on the monophonic-triangular number of a graph. This protocol has the potential to optimize routing paths, reduce latency, and increase the overall robustness of network communications. By leveraging the unique properties of mt-numbers, we can develop innovative solutions for secure and efficient data transmission, which could be particularly beneficial for applications in cybersecurity, telecommunications, and large-scale distributed systems.
In summary, our work not only advances the theoretical understanding of the mt-number in graphs but also paves the way for practical applications that could significantly impact various fields that rely on complex network structures.
There is no conflict of interest related to this work.