Monophonic eccentricities of the vertices of the graph *G* in Figure 1.

## Abstract

For any two vertices u and v in a connected graph G, a u − v path is a monophonic path if it contains no chords, and the monophonic distance dm(u, v) is the length of a longest u − v monophonic path in G. For any vertex v in G, the monophonic eccentricity of v is em(v) = max {dm(u, v) : u ∈ V}. The subgraph induced by the vertices of G having minimum monophonic eccentricity is the monophonic center of G, and it is proved that every graph is the monophonic center of some graph. Also it is proved that the monophonic center of every connected graph G lies in some block of G. With regard to convexity, this monophonic distance is the basis of some detour monophonic parameters such as detour monophonic number, upper detour monophonic number, forcing detour monophonic number, etc. The concept of detour monophonic sets and detour monophonic numbers by fixing a vertex of a graph would be introduced and discussed. Various interesting results based on these parameters are also discussed in this chapter.

### Keywords

- monophonic path
- monophonic distance
- detour monophonic number
- upper detour monophonic number
- forcing detour monophonic number
- vertex detour monophonic number
- upper vertex detour monophonic number
- forcing vertex detour monophonic number

## 1. Introduction

In this chapter, we consider a finite connected graph *G* = (*V*(*G*), *E*(*G*)) having no loops and multiple edges. The *order* and *size* of *G* are denoted by *p* and *q*, respectively. Distance in graphs is a wide branch of graph theory having numerous scientific and real-life applications. There are many kinds of distances in graphs found in literature. For any two vertices *u* and *v* in *G*, the *distance d*(*u, v*) from *u* to *v* is defined as the length of a shortest *u − v* path in *G.* The *eccentricity e*(*v*) of a vertex *v* in *G* is the maximum distance from *v* to a vertex of *G.* The *radius rad G* of *G* is the minimum eccentricity among the vertices of *G,* while the *diameter diam G* of *G* is the maximum eccentricity among the vertices of *G.* The distance between two vertices is a fundamental concept in pure graph theory, and this distance is a metric on the vertex set of *G*. More results related to this distance are found in Refs. [1, 2, 3, 4, 5, 6, 7, 8, 9]. This distance is used to study the central concepts like center, median, and centroid of a graph [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]. With regard to convexity, this distance is the basis of some geodetic parameters such as geodetic number, connected geodetic number, upper geodetic number and forcing geodetic number [23, 24, 25, 26, 27, 28, 29, 30, 31, 32]. The geodesic graphs, extremal graphs, distance regular graphs and distance transitive graphs are some important classes based on the distance in graphs [33, 34]. These concepts have interesting applications in location theory and convexity theory. The *neighborhood* of a vertex *v* is the set *N*(*v*) consisting of all vertices *u* which are adjacent with *v*. A vertex *v* is an *extreme vertex* if the subgraph induced by its neighbors is complete.

The detour distance, which is defined to be the length of a longest path between two vertices of a graph, is also a metric on the vertex set of *G* [35, 36]. For any two vertices *u* and *v* in *G*, the *detour distance D*(*u, v*) from *u* to *v* is defined as the length of a longest *u − v* path in *G.* The *detour eccentricity e*_{D}(*v*) of a vertex *v* in *G* is the maximum detour distance from *v* to a vertex of *G.* The *detour radius rad*_{D}*G* of *G* is the minimum detour eccentricity among the vertices of *G,* while the *detour diameter diam*_{D}*G* of *G* is the maximum detour eccentricity among the vertices of *G.* With regard to detour convexity, the detour number of a graph was introduced and studied in Refs. [25, 37]. The detour concepts and colorings are widely used in the channel assignment problem in FM radio technology and also in certain molecular problems in theoretical chemistry.

The parameter geodetic (detour) number of a graph is global in the sense that there is exactly one geodetic (detour) number for a graph. The concept of geodetic (detour) sets and geodetic (detour) numbers by fixing a vertex of a graph was also introduced and discussed in Refs. [38, 39, 40, 41, 42]. With respect to each vertex of a graph, there is a geodetic (detour) number, and so there will be at most as many geodetic (detour) numbers as there are vertices in the graph.

## 2. Monophonic distance

**Definition 2.1.***A chord of a path u*_{1}*, u*_{2}*,…, u*_{n}*in a connected graph G is an edge u*_{i}*u*_{j}*with j ≥ i +* 2. *A u − v path P is called a monophonic path if it is a chordless path. The length of a longest u* − *v monophonic path is called the monophonic distance from u to v*, *and it is denoted by d*_{m}(*u, v*)*. A u* − *v monophonic path with its length equal to d*_{m}(*u, v*) *is known as a u* − *v monophonic.*

**Example 2.2.** Consider the graph *G* given in Figure 1. It is easily verified that *d*(*v*_{1}*, v*_{4}) = 2*, D*(*v*_{1}*, v*_{4}) = 6, and *d*_{m}(*v*_{1}*, v*_{4}) = 4. Thus the monophonic distance is different from both the distance and the detour distance. The monophonic path *P* : *v*_{1}*, v*_{2}*, v*_{8}*, v*_{7}*, v*_{4} is *v*_{1}*− v*_{4} monophonic while the monophonic path *Q* : *v*_{1}*, v*_{3}*, v*_{4} is not *v*_{1}*− v*_{4} monophonic.

The usual distance *d* and the detour distance *D* are metrics on the vertex set *V* of a connected graph *G,* whereas the monophonic distance *d*_{m} is not a metric on *V.* For the graph *G* given in Figure 1, *d*_{m}(*v*_{4}*, v*_{6}) = 5*, d*_{m}(*v*_{4}*, v*_{5}) = 1 and *d*_{m}(*v*_{5}*, v*_{6}) = 1. Hence *d*_{m}(*v*_{4}*, v*_{6}) *> d*_{m}(*v*_{4}*, v*_{5}) + *d*_{m}(*v*_{5}*, v*_{6}), and so the triangle inequality is not satisfied.

The following result is an easy consequence of the respective definitions.

**Proposition 2.3.***Let u and v be any two vertices in a graph G of order p. then*

**Result 2.4.** Let *u* and *v* be any two vertices in a connected graph *G*. Then

*d*_{m}(*u, v*) = 0 if and only if*u*=*v.**d*_{m}(*u, v*) = 1 if and only if*uv*is an edge of*G.**d*_{m}(*u, v*) =*p −*1 if and only if*G*is the path with endvertices*u*and*v.**d*(*u, v*) =*d*_{m}(*u, v*) =*D*(*u, v*) if and only if*G*is a tree.

**Definition 2.5.***For any vertex v in a connected graph G, the monophonic eccentricity of v is e*_{m}(*v*) *= max* {*d*_{m}(*u, v*) : *u* ∈ *V*}*. A vertex u of G such that d*_{m}(*u, v*) = *e*_{m}(*v*) *is called a monophonic eccentric vertex of v. The monophonic radius and monophonic diameter of G are defined by rad*_{m}*G = min* {*e*_{m}(*v*) : *v* ∈ *V*} *and diam*_{m}*G = max* {*e*_{m}(*v*) : *v* ∈ *V*}, *respectively.*

**Example 2.6.**Table 1 shows the monophonic distance between the vertices and also the monophonic eccentricities of vertices of the graph *G* given in Figure 1. It is to be noted that *rad*_{m}*G* = 3 and *diam*_{m}*G* = 5.

d_{m}(v_{i}, v_{j}) | v_{1} | v_{2} | v_{3} | v_{4} | v_{5} | v_{6} | v_{7} | v_{8} | e_{m}(v) |
---|---|---|---|---|---|---|---|---|---|

v_{1} | 0 | 1 | 1 | 4 | 1 | 4 | 3 | 4 | 4 |

v_{2} | 1 | 0 | 4 | 3 | 1 | 5 | 4 | 1 | 5 |

v_{3} | 1 | 4 | 0 | 1 | 2 | 4 | 4 | 4 | 4 |

v_{4} | 4 | 3 | 1 | 0 | 1 | 5 | 1 | 4 | 5 |

v_{5} | 1 | 1 | 2 | 1 | 0 | 1 | 3 | 3 | 3 |

v_{6} | 4 | 5 | 4 | 5 | 1 | 0 | 1 | 1 | 5 |

v_{7} | 3 | 4 | 4 | 1 | 3 | 1 | 0 | 1 | 4 |

v_{8} | 4 | 1 | 4 | 4 | 3 | 1 | 1 | 0 | 4 |

**Remark 2.7.** In any connected graph, the eccentricity of every two adjacent vertices differs by at most 1. However, this is not true in the case of monophonic distance. For the graph *G* given in Figure 1, *e*_{m}(*v*_{5}) = 3 and *e*_{m}(*v*_{6}) = 5.

**Note 2.8.** Any two vertices *u* and *v* in a tree *T* are connected by a unique path, and so *d*(*u, v*) = *d*_{m}(*u, v*) = *D*(*u, v*). Hence *rad T* = *rad*_{m}*T* = *rad*_{D}*T* and *diam T* = *diam*_{m}*T* = *diam*_{D}*T.* The monophonic radius and the monophonic diameter of some standard graphs are given in Table 2.

Graph G | K_{p} | C_{p} | W_{1,p−1} (p ≥ 4) | K_{1,p−1} (p ≥ 2) | K_{m,n} (m,n ≥ 2) | P_{p} |
---|---|---|---|---|---|---|

rad_{m}G | 1 | p − 2 | 1 | 1 | 2 | |

diam_{m}G | 1 | p − 2 | p − 3 | 2 | 2 | p − 1 |

The next theorem follows from Proposition 2.3.

**Theorem 2.9.***For a connected graph G, the following results hold:*

*e*(*v*)*≤ e*_{m}(*v*)*≤ e*_{D}(*v*)*for any vertex v in G.**rad G ≤ rad*_{m}*G ≤ rad*_{D}*G.**diam G ≤ diam*_{m}*G ≤ diam*_{D}*G.*

**Theorem 2.10.** (*a*) *If a*, *b**and c are integers with* 3 *≤ a ≤ b ≤ c*, *then there exists a connected graph G such that rad G* = *a, rad*_{m}*G* = *b**and rad*_{D}*G* = *c.*

(*b*) *If a, b**and c are integers with* 5 *≤ a ≤ b ≤ c, then there exists a connected graph G such that diam G* = *a, diam*_{m}*G* = *b**and diam*_{D}*G* = *c.*

**Proof.** (a) The result is proved by considering three cases.

**Case (i)** 3 *≤ a* = *b* = *c.* Consider *G = P*_{2a + 1}, the path of order 2*a* + 1. It is clear that *rad G* = *rad*_{m} *G* = *rad*_{D}*G* = *a.*

**Case (ii)** 3 *≤ a ≤ b < c.* Let *F*_{1} : *u*_{1}*, u*_{2}*,…, u*_{a−1} and *F*_{2} : *v*_{1}*, v*_{2}*,…, v*_{a−1} be two copies of the path *P*_{a−1} of order *a −* 1. Let *F*_{3} : *w*_{1}*, w*_{2}*,…, w*_{b−a+3} and *F*_{4} : *z*_{1}*, z*_{2}*,…, z*_{b−a+3} be two copies of the path *P*_{b−a+3} of order *b−a*+3*,* and *F*_{5} = *K*_{c−b+1} the complete graph of order *c − b* + 1 with *V*(*F*_{5}) = {*x*_{1}*, x*_{2}*,…, x*_{c−b+1}}. We construct the graph *G* as follows: (i) identify the vertices *x*_{1} in *F*_{5} and *w*_{1} in *F*_{3}; also identify the vertices *x*_{c−b+1} in *F*_{5} and *z*_{1} in *F*_{4}; (ii) identify the vertices *w*_{b−a+3} in *F*_{3} and *u*_{2} in *F*_{1}, and identify the vertices *z*_{b−a+3} in *F*_{4} and *v*_{2} in *F*_{2}; and (iii) join each vertex *w*_{i} (1 *≤ i ≤ b−a*+2) in *F*_{3} and *u*_{1} in *F*_{1}, and join each vertex *z*_{i} (1 *≤ i ≤ b−a*+2) in *F*_{4} and *v*_{1} in *F*_{2}. The resulting graph *G* is shown in Figure 2. It is easily verified that *e*(*v*) = *a* if *v* ∈ *V*(*F*_{5}); *e*(*v*) *> a* if *v* ∈ *V*(*G*) *− V*(*F*_{5})*, e*_{m}(*v*) = *b* if *v* ∈ *V*(*F*_{5}); *e*_{m}(*v*) *> b* if *v* ∈ *V*(*G*) *− V*(*F*_{5}) and *e*_{D}(*v*) = *c* if *v* ∈ *V*(*F*_{5}); and *e*_{D}(*v*) *> c* if *v* ∈ *V*(*G*) *− V*(*F*_{5}). It follows that *rad G* = *a, rad*_{m}*G* = *b*, and *rad*_{D}*G* = *c.*

**Case (iii)** 3 *≤ a < b* = *c.* Let *E*_{1} : *v*_{1}*, v*_{2}*,…, v*_{2a+1} be a path of order 2*a* + 1. Let *E*_{2} : *u*_{1}*, u*_{2}*,…, u*_{b−a+3} and *E*_{3}: *w*_{1}*, w*_{2}*,…, w*_{b−a+3} be two copies of the path *P*_{b−a+3} of order *b − a* + 3, and let *E*_{i} (4 *≤ i ≤* 2(*b − a*) + 3) be 2(*b − a*) copies of *K*_{1}. We construct the graph *G* as follows: (i) identify the vertices *v*_{a+1} in *E*_{1}*, u*_{1} in *E*_{2}*,* and *w*_{1} in *E*_{3}; (ii) identify the vertices *v*_{a−1} in *E*_{1} and *u*_{b−a+3} in *E*_{2}, and identify the vertices *v*_{a+3} in *E*_{1} and *w*_{b−a+3} in *E*_{3}; and (iii) join each *E*_{i} (4 *≤ i ≤ b* − *a* + 3) with *v*_{a+1} in *E*_{1} and *u*_{i−1} in *E*_{2}, and join each *E*_{i} (*b − a* + 4 *≤ i ≤* 2(*b − a*) + 3) with *v*_{a+1} in *E*_{1} and *w*_{i−b+a−1} in *E*_{3}. The resulting graph *G* is shown in Figure 3.

It is easily verified that *e*(*v*_{a+1}) = *a*; *e*(*v*) *> a* if *v* ∈ *V*(*G*) *−* {*v*_{a+1}}; *e*_{m}(*v*_{a+1}) = *b*; *e*_{m}(*v*) *> b* if *v* ∈ *V*(*G*) *−* {*v*_{a+1}}*,* and *e*_{D}(*v*_{a+1}) = *c*; and *e*_{D}(*v*) *> c* if *v* ∈ *V*(*G*) *−* {*v*_{a+1}}. It follows that *rad G* = *a, rad*_{m}*G* = *b*, and *rad*_{D}*G* = *c.*

(b) This result is also proved by considering three cases.

**Case (i)** 5 *≤ a* = *b* = *c.* Let *G* be a path of order *a*+1. Then *diam G* = *diam*_{m}*G* = *diam*_{D}*G* = *a.*

**Case (ii)** 5 *≤ a ≤ b < c.* Let *F*_{1} : *u*_{1}*, u*_{2}*,…, u*_{a−1} be the path *P*_{a−1} of order *a −* 1*; F*_{2} : *w*_{1}*, w*_{2}*,…, w*_{b−a+3} be the path *P*_{b−a+3} of order *b − a* + 3*;* and *F*_{3} = *K*_{c−b+1} be the complete graph of order *c* − *b* +1 with *V* (*F*_{3}) = {*x*_{1}*, x*_{2}*,…, x*_{c−b+1}}. We construct the graph *G* as follows: (i) identify the vertices *x*_{1} in *F*_{3} and *w*_{1} in *F*_{2}, and identify the vertices *w*_{b−a+3} in *F*_{2} and *u*_{2} in *F*_{1}, and (ii) join each vertex *w*_{i} (1 *≤ i ≤ b* − *a* + 2) in *F*_{2} and *u*_{1} in *F*_{1}. The resulting graph *G* is shown in Figure 4. It is easily verified that *e*(*v*) = *a* if *v* ∈ (*V*(*F*_{3}) *−* {*x*_{1}}) *∪* {*u*_{a−1}}; *e*(*v*) *< a* if *v* ∈ *V*(*F*_{2}) *∪* (*V*(*F*_{1}) *−* {*u*_{a−1}})*,* and *e*_{m}(*v*) = *b* if *v* ∈ (*V*(*F*_{3}) *−* {*x*_{1}}) *∪* {*u*_{a−1}}; *e*_{m}(*v*) *< b* if *v* ∈ *V*(*F*_{2}) *∪* (*V*(*F*_{1}) *−* {*u*_{a−1}})*,* and *e*_{D}(*v*) = *c* if *v* ∈ (*V*(*F*_{3}) *−* {*x*_{1}}) *∪* {*u*_{a−1}}; and *e*_{D}(*v*) *< c* if *v* ∈ *V*(*F*_{2}) *∪* (*V*(*F*_{1}) *−* {*u*_{a−1}}). It follows that *diam G* = *a, diam*_{m}*G* = *b* and *diam*_{D}*G* = *c.*

**Case (iii)** 5 *≤ a < b* = *c.* Let *E*_{1} : *v*_{1}*, v*_{2}*,…, v*_{a+1} be a path of order *a* + 1; *E*_{2} : *w*_{1}*, w*_{2}*,…, w*_{b−a+3} be another path of order *b* − *a* + 3; and *E*_{i} (3 *≤ i ≤ b − a* + 2) be *b − a* copies of *K*_{1}. Let *G* be the graph obtained from *E*_{i} for *i* = 1*,* 2*,…, b* − *a* + 2 by identifying the vertices *v*_{a−2} and *v*_{a} of *E*_{1} with *w*_{1} and *w*_{b−a+3} of *E*_{2}, respectively, and joining each *E*_{i} (3 *≤ i ≤ b* − *a* + 2) with *v*_{a−2} and *w*_{i}. The graph *G* is shown in Figure 5.

It is easily verified that *e*(*v*) = *a* if *v* ∈ {*v*_{1}*, v*_{a+1}}; *e*(*v*) *≤ a* if *v* ∈ *V*(*G*) *−* {*v*_{1}*, v*_{a+1}}*,* and *e*_{m}(*v*) = *b* if *v* ∈ {*v*_{1}*, v*_{a+1}}; *e*_{m}(*v*) *≤ b* if *v* ∈ *V*(*G*) *−* {*v*_{1}*, v*_{a+1}}*,* and *e*_{D}(*v*) = *c* if *v* ∈ {*v*_{1}*, v*_{a+1}}; and *e*_{D}(*v*) *≤ c* if *v* ∈ *V*(*G*) *−* {*v*_{1}*, v*_{a+1}}. It follows that *rad G* = *a, rad*_{m}*G* = *b* and *rad*_{D}*G* = *c.*

For any connected graph *G*, the inequalities *rad G ≤ diam G ≤* 2 *rad G* and *rad*_{D}*G ≤ diam*_{D}*G ≤* 2 *rad*_{D}*G* hold. However, this is not true in the case of monophonic radius and monophonic diameter. For example, when the graph *G* is the wheel *W*_{1,p−1} (*p ≥* 6)*,* it is easily seen that *rad*_{m}*G* = 1 and *diam*_{m}*G* = *p −* 3 *≥* 3 so that *diam*_{m}*G >* 2 *rad*_{m}*G.*

It is proved in Ref. [6] that if *a* and *b* are any two positive integers such that *a ≤ b ≤* 2*a*, then there is a connected graph *G* with *rad G* = *a* and *diam G* = *b.* Also, it is proved in Ref. [35] that if *a* and *b* are any two positive integers such that *a ≤ b ≤* 2*a*, then there is a connected graph *G* with *rad*_{D}*G* = *a* and *diam*_{D}*G* = *b.*

Now, the following theorem gives a realization result for *rad*_{m}*G* ≤ *diam*_{m}*G.*

**Theorem 2.11.***If a and b are positive integers with a ≤ b, then there exists a connected graph G such that rad*_{m}*G* = *a and diam*_{m}*G* = *b.*

**Proof.** This result is proved by considering three cases.

**Case (i)***a* = *b ≥* 1. Let *G* be the cycle *C*_{a+2}. Then *rad*_{m}*G* = *a* and *diam*_{m}*G* = *b.*

**Case (ii)***a < b ≤* 2*a.* Let *C*_{1} : *u*_{1}*, u*_{2}*,…, u*_{a+2}*, u*_{1} be a cycle of order *a* + 2 and *C*_{2} : *v*_{1}*, v*_{2}*,…, v*_{b−a+2}*, v*_{1} be a cycle of order *b − a* + 2. Let *G* be the graph obtained by identifying the vertex *u*_{1} of *C*_{1} and *v*_{1} of *C*_{2}. Since *b ≤* 2*a,* it follows that *b − a* + 2 *≤ a* + 2. It is clear that *d*_{m}(*u*_{1}*, x*) *≤ a* for any *x* in *G* and *d*_{m}(*u*_{1}*, u*_{a+1}) = *a.* Therefore, *e*_{m}(*u*_{1}) = *a.* Also, it is clear that there is no vertex *x* with *e*_{m}(*x*) *< a* and so *rad*_{m}*G* = *a.* It is clear that *d*_{m}(*u*_{3}*, v*_{3}) = *b* and *d*_{m}(*u*_{3}*, x*) *≤ b* for any vertex *x* in *G* and so *e*_{m}(*u*_{3}) = *b.* Also, it is easy to see that *e*_{m}(*x*) ≤ *b* for every vertex *x* in *G* so that *diam*_{m}*G* = *b.*

**Case (iii)***b >* 2*a.* Let *G* be the graph obtained by identifying the central vertex of the wheel *W* = *K*_{1} + *C*_{b+2} (*b ≥* 2) and an endvertex of the path *P*_{2a}. Since *b >* 2*a, e*_{m}(*x*) = *b* for any vertex *x* ∈ *V*(*C*_{b+2}). Also, *a ≤ e*_{m}(*x*) *≤* 2*a* for any vertex *x* ∈ *V*(*P*_{2a}) and *e*_{m}(*v*_{a}) = *a.* Hence *rad*_{m}*G* = *a* and *diam*_{m}*G* = *b.*

### 2.1. Monophonic center and monophonic periphery

**Definition 2.12.***A vertex v in a connected graph G is called a monophonic central vertex if e*_{m}(*v*) = *rad*_{m}*G*, *and the subgraph induced by the monophonic central vertices of G is the monophonic center C*_{m}(*G*) *of G. A vertex v in G is called a monophonic peripheral vertex if e*_{m}(*v*) = *diam*_{m}*G*, *and the subgraph induced by the monophonic peripheral vertices of G is the monophonic periphery P*_{m}(*G*) *of G.*

**Example 2.13.** Consider the graph *G* given in Figure 1. It is easily verified that *v*_{5} is the monophonic central vertex and *v*_{2}*, v*_{4}, and *v*_{6} are the monophonic peripheral vertices of *G*.

**Remark 2.14.** The monophonic center of a connected graph *need* not be connected. For the graph *G* given in Figure 6, *C*_{m}(*G*) = {*v*_{3}*, v*_{6}}.

**Theorem 2.15.***Every graph is the monophonic center of some connected graph.*

**Proof.** Let *G* be a graph. We show that *G* is the monophonic center of some graph. Let *l* = *d*_{m} be the monophonic diameter of *G*. Let *P* : *u*_{1}*, u*_{2}*,…, u*_{l} and *Q* : *v*_{1}*, v*_{2}*,…, v*_{l} be two copies of the path *P*_{l}. The required graph *H* given in Figure 7 is got from *G, P*, and *Q* by joining each vertex of *G* with *u*_{1} in *P* and *v*_{1} in *Q.* Then *e*_{mH}(*x*) = *d*_{m} for each vertex *x* in *G* and *d*_{m} + 1 *≤ e*_{mH}(*x*) *≤* 2 *d*_{m} for each vertex *x* not in *G*. Therefore, *V*(*G*) is the set of monophonic central vertices of *H* and so *C*_{m}(*H*) = *G*.

More specifically, it is proved in Ref. [43] that the center of every connected graph *G* lies in a single block of *G.* Also, it is proved in Ref. [35] that the detour center of every connected graph *G* lies in a single block of *G.* The same result is true for the monophonic center also, as proved in the following theorem.

**Theorem 2.16.***The monophonic center C*_{m}(*G*) *of every connected graph G is a subgraph of some block of G.*

**Proof.** Suppose that there is a connected graph *G* such that its monophonic center *C*_{m}(*G*) is not a subgraph of a single block of *G.* Then *G* has a cut vertex *v* such that *G − v* contains two components *H*_{1} and *H*_{2}*,* each containing vertices of *C*_{m}(*G*). Let *u* be a vertex of *G* such that *e*_{m}(*v*) = *d*_{m}(*u,v*), and let *P*_{1} be a *u − v* longest monophonic path in *G.* Then at least one of *H*_{1} and *H*_{2} contains no vertices of *P*_{1}, say *H*_{2} contains no vertex of *P*_{1}. Now, take a vertex *w* in *C*_{m}(*G*) that belongs to *H*_{2}, and let *P*_{2} be a *v − w* longest monophonic path in *G.* Since *v* is a cut vertex, *P*_{1} followed by *P*_{2} gives a *u − w* longest monophonic path with its length greater than that of *P*_{1}. This gives *e*_{m}(*w*) *> e*_{m}(*v*) so that *w* is not a monophonic central vertex of *G,* which is a contradiction.

**Corollary 2.17.***For any tree, the monophonic center is isomorphic to K*_{1}*or K*_{2}.

It is proved in Ref. [44] that a nontrivial graph *G* is the periphery of some connected graph if and only if every vertex of *G* has eccentricity 1 or no vertex of *G* has eccentricity 1. Also, it is proved in Ref. [35] that a connected graph *G* of order *p ≥* 3 and radius 1 is the detour periphery of some connected graph if and only if *G* is Hamiltonian. A similar result is given in the next theorem, and for a proof, one may refer to Ref. [45].

**Theorem 2.18.***A nontrivial graph G is the monophonic periphery of some connected graph if and only if every vertex of G has monophonic eccentricity* 1 *or no vertex of G has monophonic eccentricity* 1.

**Definition 2.19.***A connected graph G is monophonic self-centered if rad*_{m}*G = diam*_{m}*G, that is, if G is its own monophonic center.*

**Example 2.20.** The complete graph *K*_{n}*,* the cycle *C*_{n}, and the complete bipartite graph *K*_{m,n} (*m, n ≥* 2) are monophonic self-centered graphs.

The following problem is left open.

**Problem 2.21.***Characterize monophonic self-centered graphs*.

Further results on monophonic distance in graphs can be found in Refs. [45, 46].

## 3. Detour monophonic number

Throughout this section, by a *u − v* detour monophonic path, we mean a longest *u − v* monophonic path.

**Definition 3.1.***A set S of vertices of a connected graph G is called a detour monophonic set if every vertex of G lies on a u − v detour monophonic path for some u*, *v* ∈ *S*. *The detour monophonic number of G is defined as the minimum cardinality of a detour monophonic set of G and is denoted by dm*(*G*).

**Example 3.2**. For the graph *G* given in Figure 8, *S*_{1} = {*v*_{1}, *v*_{2}, *v*_{3}}, *S*_{2} = {*v*_{2}, *v*_{3}, *v*_{4}}, *S*_{3} = {*v*_{5}, *v*_{6}, *v*_{2}}, *S*_{4} = {*v*_{5}, *v*_{6}, *v*_{3}}, *S*_{5} = {*v*_{1}, *v*_{3}, *v*_{5}}, *S*_{6} = {*v*_{1}, *v*_{3}, *v*_{6}}, *S*_{7} = {*v*_{2}, *v*_{4}, *v*_{5}}, and *S*_{8} = {*v*_{2}, *v*_{4}, *v*_{6}} are the minimum detour monophonic sets of *G* and so *dm*(*G*) = 3.

If a vertex belongs to every minimum detour monophonic set of *G*, then it is called a *detour monophonic vertex* of *G*. If *S* is the unique minimum detour monophonic set of *G*, then *S* is the set of all detour monophonic vertices of *G*. In the next theorem, we show that there are certain vertices in a nontrivial connected graph *G* that are detour monophonic vertices of *G*.

**Theorem 3.3.***Every detour monophonic set of a connected graph G contains all its extreme vertices. Moreover, if the set of all extreme vertices S of G is a detour monophonic set of G, then S is the unique minimum detour monophonic set of G*.

**Proof.** Let *v* be an extreme vertex and let *S* be a detour monophonic set of *G*. If *v* is not an element of *S*, then there exist two elements *x* and *y* in *S* such that *v* is an internal vertex of an *x* − *y* detour monophonic path, say *P*. Let *u* and *w* be the vertices on *P* adjacent to *v*. Then *u* and *w* are not adjacent and so *v* is not an extreme vertex of *G*, which is a contradiction. Therefore *v* belongs to every detour monophonic set of *G*. Thus, if *S* is the set of all extreme vertices of *G*, then *dm*(*G*) ≥ |*S*|. On the other hand, if *S* is a detour monophonic set of *G*, then *dm*(*G*) ≤ |*S*|. Therefore *dm*(*G*) = |*S*| and *S* is the unique minimum detour monophonic set of *G*.

The following two theorems are easy to prove.

**Theorem 3.4.***Let G be a connected graph with a cut vertex v**and let S be a detour monophonic set of G. Then every component of G − v contains an element of S.*

**Theorem 3.5.***No cut vertex of a connected graph G belongs to any minimum detour monophonic set of G.*

Since every end-block *B* is a branch of *G* at some cut vertex, it follows Theorem 3.4 and Theorem 3.5 that every minimum detour monophonic set of *G* contains at least one vertex from *B* that is not a cut vertex. Thus the following corollaries are consequences of Theorems 3.4 and 3.5.

**Corollary 3.6.***If G is a connected graph with k ≥ 2 end-blocks, then dm(G) ≥ k.*

**Corollary 3.7.***If k is the maximum number of blocks to which a vertex in a graph G belongs, then dm(G) ≥ k.*

**Theorem 3.8.***For any connected graph G, 2 ≤ dm(G) ≤ p.*

**Theorem 3.9.***For any connected graph G, dm(G) = p if and only if G is complete*.

**Proof.** Let *dm*(*G*) = *p*. Suppose that *G* is not a complete graph. Then there exist two vertices *u* and *v* such that *u* and *v* are not adjacent in *G*. Since *G* is connected, there is a detour monophonic path from *u* to *v*, say *P*, with length at least 2. Clearly, (*V*(*G*) − *V*(*P*)) *∪* {*u*, *v*} is a detour monophonic set of *G* and hence *dm*(*G*) ≤ *p* − 1, which is a contradiction. Conversely, if *G* is complete, then by Theorem 3.3, *dm*(*G*) = *p*.

**Theorem 3.10.***If G is a nontrivial connected graph of order p and monophonic diameter d, then dm(G) ≤ p − d +* 1.

**Proof.** Let *x*, *y* ∈ *V*(*G*) such that *G* contains an *x* − *y* detour monophonic path *P* of length *diam*_{m}*G* = *d*. Let *S* = (*V*(*G*)−*V*(*P*)) *∪* {*x*, *y*}. Since *S* is a detour monophonic set of *G*, it follows that *dm*(*G*) ≤ |*S*| ≤ *p* − *d* + 1.

**Theorem 3.11.***For every nontrivial tree T of order p and monophonic diameter d, dm(T) = p − d +* 1 *if and only if T is a caterpillar*.

**Proof.** Let *T* be any nontrivial tree. Let *P* : *u* = *v*_{0}, *v*_{1},…, *v*_{d} be a monophonic diametral path. Let *k* be the number of endvertices of *T* and let *l* be the number of internal vertices of *T* other than *v*_{1}, *v*_{2},…, *v*_{d−1}. Then *d* − 1 + *l* + *k* = *p*. By Theorem 3.3 and Theorem 3.5, *dm*(*T*) = *k* and so *dm*(*T*) = *p* − *d* − *l* + 1. Hence *dm*(*T*) = *p* − *d* + 1 if and only if *l* = 0, if and only if all the internal vertices of *T* lie on the monophonic diametral path *P*, and if and only if *T* is a caterpillar.

It is known that *rad*_{m}*G* ≤ *diam*_{m}*G* for a connected graph *G*. It is proved in Ref. [45] that if *a* and *b* are any two positive integers such that *a* ≤ *b*, then there is a connected graph *G* with *rad*_{m}*G* = *a* and *diam*_{m}*G* = *b*. The same result can also be extended so that the detour monophonic number can be prescribed when *rad*_{m}*G* < *diam*_{m}*G,* and for a proof, one may refer to Ref. [47].

**Theorem 3.12.***For positive integers r*, *d**and n ≥ 4 with r < d, there exists a connected graph G with rad*_{m}*G = r, diam*_{m}*G = d**and dm(G) = n*.

**Problem 3.13.** For any three positive integers *r*, *d* and *n* ≥ 4 with *r* = *d*, does there exist a connected graph *G* with *rad*_{m}*G* = *r*, *diam*_{m}*G* = *d* and *dm*(*G*) = *n*?

### 3.1. Upper detour monophonic number

**Definition 3.14.***A detour monophonic set S of a connected graph G is called a minimal detour monophonic set if no proper subset of S is a detour monophonic set of G. The maximum cardinality of a minimal detour monophonic set of G is the upper detour monophonic number of G, denoted by dm*^{+}(*G*).

**Example 3.15.** Consider the graph *G* given in Figure 8. The minimal detour monophonic sets are *S*_{1} = {*v*_{1}, *v*_{2}, *v*_{3}}, *S*_{2} = {*v*_{2}, *v*_{3}, *v*_{4}}, *S*_{3} = {*v*_{5}, *v*_{6}, *v*_{2}}, *S*_{4} = {*v*_{5}, *v*_{6}, *v*_{3}}, *S*_{5} = {*v*_{1}, *v*_{3}, *v*_{5}}, *S*_{6} = {*v*_{1}, *v*_{3}, *v*_{6}}, *S*_{7} = {*v*_{2}, *v*_{4}, *v*_{5}}, *S*_{8} = {*v*_{2}, *v*_{4}, *v*_{6}} and *S*_{9} = {*v*_{1}, *v*_{4}, *v*_{5}, *v*_{6}}. For this graph, the upper detour monophonic number is 4, and the detour monophonic number is 3.

**Note 3.16.** Every minimum detour monophonic set is a minimal detour monophonic set, but the converse is not true. For the graph *G* given in Figure 8, *S*_{9} is a minimal detour monophonic set, but it is not a minimum detour monophonic set of *G*.

The following three theorems are easy to prove.

**Theorem 3.17.***For any connected graph G, 2 ≤ dm(G) ≤ dm*^{+}*(G) ≤ p*.

**Theorem 3.18.***For a connected graph G, dm(G) = p if and only if dm*^{+}*(G) = p.*

**Theorem 3.19.***If G is a connected graph of order p with dm(G) = p −* 1*, then dm*^{+}*(G) = p −* 1.

The next theorem is an interesting realization result, and for a proof, one may refer to Ref. [48].

**Theorem 3.20.***For any three positive integers a, b and n with* 2 *≤ a ≤ n ≤ b, there is a connected graph G with dm(G) = a, dm*^{+}*(G) = b and a minimal detour monophonic set of cardinality n.*

### 3.2. Forcing detour monophonic number

A connected graph *G* may contain more than one minimum detour monophonic sets. For example, the graph *G* given in Figure 8 contains eight minimum detour monophonic sets. For each minimum detour monophonic set *S* in *G*, there is always some subset *T* of *S* that uniquely determines *S* as the minimum detour monophonic set containing *T*. Such sets are called “forcing detour monophonic subsets” and these sets are discussed in this section.

**Definition 3.21.***Let S be a minimum detour monophonic set of a connected graph G. A subset S′ of S is a forcing detour monophonic subset for S if S is the unique minimum detour monophonic set that contains S′. A forcing detour monophonic subset for S of minimum cardinality is a minimum forcing detour monophonic subset of S. The cardinality of a minimum forcing detour monophonic subset of S is the forcing detour monophonic number fdm*(*S*) *in G. The forcing detour monophonic number of G is fdm*(*G*) = *min* {*fdm*(*S*)}*, where the minimum is taken over all minimum detour monophonic sets S in G.*

**Example 3.22.***For the graph G given in*Figure 9*, S*_{1} = {*z*, *w*, *v*}, *S*_{2} = {*z*, *w*, *u*} *and S*_{3} = {*z*, *w*, *x*} *are the minimum detour monophonic sets of G. It is clear that fdm*(*S*_{1}) = 1*, fdm*(*S*_{2}) = 1 *and fdm*(*S*_{3}) = 1 *so that fdm*(*G*) = 1*. For the graph G given in*Figure 10*, S* = {*y*, *v*} *is the unique minimum detour monophonic set of G and so fdm*(*G*) = 0.

The next theorem follows immediately from the definitions of the detour monophonic number and the forcing detour monophonic number of a graph *G*.

**Theorem 3.23.***For a connected graph G,* 0 ≤ *fdm*(*G*) ≤ *dm*(*G*) ≤ *p.*

The following theorem characterizes graphs *G* for which *fdm*(*G*) = 0, *fdm*(*G*) = 1 and *fdm*(*G*) = *dm*(*G*). The proof is an easy consequence of the definitions of the detour monophonic number and the forcing detour monophonic number.

**Theorem 3.24.***Let G be a connected graph. Then*

*fdm*(*G*) = 0*if and only if G contains exactly one minimum detour monophonic set.**fdm*(*G*) = 1*if and only if G contains two or more minimum detour monophonic sets, one of which is a unique minimum detour monophonic set that contains one of its elements.**fdm*(*G*) =*dm*(*G*)*if and only if no minimum detour monophonic set of G is the unique minimum detour monophonic set that contains any of its proper subsets.*

The next theorem gives a realization result for the parameters *fdm*(*G*) and *dm*(*G*), and for a proof, the reader may refer to Ref. [49].

**Theorem 3.25.***For every pair a, b of positive integers with* 0 ≤ *a* < *b and b* ≥ 2*, there exists a connected graph G such that fdm*(*G*) = *a and dm*(*G*) = *b.*

Further results on detour monophonic concepts in graphs can be found in Refs. [47, 48, 49, 50].

## 4. Vertex detour monophonic number

The parameter detour monophonic number of a graph is global in the sense that there is exactly one detour monophonic number for a graph. The concept of detour monophonic sets and detour monophonic numbers by fixing a vertex of a graph was also introduced and discussed in this section. With respect to each vertex of a graph, there is a detour monophonic number, and so there will be at most as many detour monophonic numbers as there are vertices in the graph.

**Definition 4.1.***For any vertex x in a connected graph G, a set S*_{x}*of vertices in G is called an x-detour monophonic set if every vertex of G lies on an x − y detour monophonic path in G for some y in S*_{x}*. The x-detour monophonic number of G, denoted by dm*_{x}(*G*), *is defined to be the minimum cardinality of an x-detour monophonic set of G*. *An x-detour monophonic set of cardinality dm*_{x}(*G*) *is called a dm*_{x}*-set of G*.

It is easy to observe that for any vertex *x* in *G*, *x* does not belong to any *dm*_{x}-set of *G*.

**Example 4.2.** For the graph *G* given in Figure 11, the minimum vertex detour monophonic sets and the vertex detour monophonic numbers are given in Table 3.

Vertex | Minimum vertex detour monophonic sets | Vertex detour monophonic number |
---|---|---|

t | {z,w} | 2 |

y | {w,z,t}, {w,z,u} | 3 |

z | {u,w}, {w,y} | 2 |

u | {w,z,y} | 3 |

v | {w,t,z}, {w,u,z} | 3 |

w | {t,z}, {z,u} | 2 |

The next two theorems are easy to prove.

**Theorem 4.3.***For any vertex x in a connected graph G, the following results hold.*

*Every dm*_{x}*-set of G contains all its extreme vertices other than the vertex x*(*whether x is extreme vertex or not*).*No dm*_{x}*-set of G contains a cut vertex of G.*

**Theorem 4.4.***For any vertex x in a connected graph G of order p*, 1 ≤ *dm*_{x}(*G*) ≤ *p* − 1.

**Theorem 4.5.***For any vertex x in a connected graph G of order p*, *dm*_{x}(*G*) = *p* − 1 *if and only if deg x* = *p* − 1.

**Proof**. Let *x* be any vertex in a connected graph *G* of order *p*. Let *dm*_{x}(*G*) = *p* − 1. If *deg x* < *p*−1, then there is a vertex *u* in *G* that is not adjacent to *x*. Since *G* is connected, there is a detour monophonic path from *x* to *u*, say *P*, with length greater than or equal to 2. Then (*V*(*G*)−*V*(*P*)) ∪ {*u*} is an *x-*detour monophonic set of *G* so that *dm*_{x}(*G*) ≤ *p* − 2, which is a contradiction. Conversely, let *deg x* = *p* − 1. Hence *x* is adjacent to all other vertices of *G.* This shows that all these vertices form the *dm*_{x}-set of *G* and so *dm*_{x}(*G*) = *p* − 1.

**Corollary 4.6.***A graph G is complete if and only if dm*_{x}(*G*) = *p* − 1 *for every vertex x in G*.

### 4.1. Upper vertex detour monophonic number

**Definition 4.7.***Let x be any vertex of a connected graph G. An x-detour monophonic set S*_{x}*is called a minimal x-detour monophonic set if no proper subset of S*_{x}*is an x-detour monophonic set. The upper x-detour monophonic number is the maximum cardinality of a minimal x-detour monophonic set of G and is denoted by dm*_{x}^{+}(*G*).

**Example 4.8**. For the graph *G* given in Figure 12, the minimum vertex detour monophonic sets the vertex detour monophonic numbers, the minimal vertex detour monophonic sets and the upper vertex detour monophonic numbers are given in Table 4.

Vertex x | Minimum x-detour monophonic sets | dm_{x}(G) | Minimal x-detour monophonic sets | dm_{x}^{+}(G) |
---|---|---|---|---|

t | {u,y}, {u,z} | 2 | {u,y}, {u,z} | 2 |

u | {t,y}, {t,z} | 2 | {t,y}, {t,z} | 2 |

v | {w,y}, {z,y} | 2 | {w,y}, {z,y}, {w,t,u} | 3 |

w | {z,y}, {z,v} | 2 | {z,y}, {z,v}, {v,t,u} | 3 |

y | {v,z}, {v,t}, {v,u} | 2 | {v,z}, {v,t}, {v,u}, {t,u,w} | 3 |

z | {w,y}, {w,t}, {w,u} | 2 | {w,y}, {w,t}, {w,u}, {v,t,u} | 3 |

Since every minimum *x*-detour monophonic set is a minimal *x*-detour monophonic set, we have 1 ≤ *dm*_{x}(G) ≤ *dm*_{x}^{+}(*G*) ≤ *p* − 1. In view of this, we have the following theorems, and for proofs one may refer to Ref. [51].

**Theorem 4.9.***Let x be any vertex in a connected graph G of order p ≥ 3. If dm*_{x}*(G) = 1, then dm*_{x}^{+}(*G*) *≤ p − 2*.

**Theorem 4.10.***Let x be any vertex in a connected graph G. Then dm*_{x}(*G*) = *p* − 1 *if and only if dm*_{x}^{+}(*G*) = *p* − 1.

**Theorem 4.11.***For any four integers j, k, l and p with* 2 ≤ *j* ≤ *k* ≤ *l* ≤ *p* − 7, *there exists a connected graph G of order p with dm*_{x}(*G*) = *j*, *dm*_{x}^{+}(*G*) = *l and a minimal x-detour monophonic set of cardinality k.*

### 4.2. Forcing vertex detour monophonic number

**Definition 4.12.***Let x be any vertex of a connected graph G**and let S*_{x}*be a minimum x-detour monophonic set of G. A subset S′ of S*_{x}*is an x-forcing subset for S*_{x}*if S*_{x}*is the unique minimum x-detour monophonic set that contains S′. An x-forcing subset for S*_{x}*of minimum cardinality is a minimum x-forcing subset of S*_{x}*. The cardinality of a minimum x-forcing subset of S*_{x}*is the forcing x-detour monophonic number fdm*_{x}(S_{x}) *in G. The forcing x-detour monophonic number of G is fdm*_{x}(*G*) = min { *fdm*_{x}(*S*_{x})}*, where the minimum is taken over all minimum x-detour monophonic sets S*_{x}*in G.*

**Definition 4.13.***Let x be any vertex of a connected graph G. The upper forcing x-detour monophonic number, fdm*_{x}^{+}(*G*)*, of G is the maximum forcing x-detour monophonic number among all minimum x-detour monophonic sets of G.*

**Example 4.14.** For the graph *G* given in Figure 13, the minimum vertex detour monophonic sets, the vertex detour monophonic numbers, the forcing vertex detour monophonic sets, the forcing vertex detour monophonic numbers and the upper forcing vertex detour monophonic numbers are given in Table 5.

Vertex x | dm_{x}-sets | dm_{x}(G) | x-forcing subsets | fdm_{x}(G) | fdm_{x}^{+}(G) |
---|---|---|---|---|---|

t | {v,w}, {y,z}, {w,y} | 2 | {v}, {z}, {w,y} | 1 | 2 |

u | {t,v,w}, {t,y,z}, {t,w,y} | 3 | {v}, {z}, {w,y} | 1 | 2 |

v | {t,z} | 2 | Φ | 0 | 0 |

w | {t,v}, {t,z} | 2 | {v}, {z} | 1 | 1 |

y | {t,v}, {t,z} | 2 | {v}, {z} | 1 | 1 |

z | {t,v} | 2 | Φ | 0 | 0 |

**Theorem 4.15.***For any vertex x in a connected graph G,* 0 *≤ fdm*_{x}(*G*) ≤ *fdm*_{x}^{+}(*G*) *≤ dm*_{x}(*G*).

The following theorem gives a realization result for the parameters *fdm*_{x}(*G*), *fdm*_{x}^{+}(*G*), *dm*_{x}(*G*), and for a proof, one may refer to Ref. [52].

**Theorem 4.16.***For any three integers r, s and t with* 2 ≤ *r* ≤ *s* ≤ *t* with 2*r* − *s* ≥ 0, *there exists a connected graph G with fdm*_{x}(*G*) = *r*, *fdm*_{x}^{+}(*G*) = *s**and dm*_{x}(*G*) = *t for some vertex x in G*.

There are useful applications of these concepts to security-based communication network design. In the case of designing the channel for a communication network, although all the vertices are covered by the network when considering detour monophonic sets, some of the edges may be left out. This drawback is rectified in the case of edge detour monophonic sets so that considering edge detour monophonic sets is more advantageous to real-life application of communication networks. The edge detour monophonic sets are discussed in Refs. [53, 54, 55].

## 5. Conclusion

In this chapter, the new distance known as monophonic distance in a graph is introduced, and its properties are studied. Its relationship with the usual distance and detour distance is discussed. Various realization theorems are proved with regard to the radius (diameter), monophonic radius (monophonic diameter) and detour radius (detour diameter). Results regarding monophonic center and monophonic periphery of a graph are presented. Further, the concept of a detour monophonic set in a graph is introduced and its various properties are presented. Consequently, the parameters, viz., detour monophonic number, upper detour monophonic number and forcing detour monophonic number of a graph are introduced and studied. In a similar way, the vertex detour monophonic number, the upper vertex detour monophonic number and the forcing vertex detour monophonic number of a graph are introduced and studied. Many interesting characterization theorems and also realization theorems with regard to all these parameters are presented. The results presented in this chapter would help the researchers in graph theory to develop new results and applications to various branches of science.