The Monophonic-triangular Number of a Graph

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^{\prime }=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^{\prime }$ is an mt-set of $G$, it contradicts to $M$ a minimum mt-set of $G$.

 

Proof.

1. 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 $\mathit{\text{mt}}$-set of $K_p$ and so $\mathit{\text{mt}}(K_p)=2$.

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 $\mathit{\text{mt}}$-set of $C_p$ and so $\mathit{\text{mt}}(C_p)=2$.

3. 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 $\mathit{\text{mt}}$-set of $W_p$ and so $\mathit{\text{mt}}(W_p)=2$.

4. 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 $\mathit{\text{mt}}(K_{m,n})=\left|M\right|=m$. When $m\ge 4$, 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$.

Proof. Let $P:a=a_0,a_1,\dots ,a_d=b$ be an $a-b$ $mt$-path of length $d=dia{m}_{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-dia{m}_{mt}(G)+1$. 

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, $dia{m}_{mt}(G)\ge 2$. Then by Theorem 7, $mt(G)\le p-dia{m}_{mt}(G)+1\le p-1$, it contradicts our assumption. Hence $G=K_2$. 

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. 

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^{\prime }=M\cup \{y_1\}$. As a result, a minimum mt-set of $G$ is $M^{\prime }$ and hence $mt(G)=p-2$.

Conversely, let $G$ be a graph of order $p\ge 5$ such that $mt(G)=p-2$. Then by Theorem 1, $dia{m}_{mt}(G)\ge 2$. If $dia{m}_{mt}(G)\ge 4$, then by Theorem 7, $mt(G)\le p-3$, it contradicts our assumption. Hence $dia{m}_{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 $dia{m}_{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\ge 5$ 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 $dia{m}_{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 $dia{m}_{mt}(G)\ge 4$, it contradicts our assumption. Thus exactly one vertex in $C_3$ has degree 3 or more. Since $dia{m}_{mt}(G)=3$, it follows that $G=K_{1,p-1}+e$.

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)\le m(G)\le g(G)$. Then the result follows from Proposition 1. 

Proof. If $2\le 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\le i\le 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^{\prime }=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^{\prime }$ is included in each monophonic set of $G$. Obviously, $M^{\prime }$ is a monophonic set of $G$ and hence $m(G)=|M^{\prime }|=l$. Now, by Theorem 4, every member of $M^{\prime }$ 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^{\prime }$. As a result, $M^{\prime }$ is not a geodetic set of $G$ and hence $g(G)>|M^{\prime }|$. 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^{\prime }\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. 

Proof.