Open access peer-reviewed chapter

Monophonic Distance in Graphs

By P. Titus and A.P. Santhakumaran

Submitted: October 14th 2016Reviewed: March 20th 2017Published: December 20th 2017

DOI: 10.5772/intechopen.68668

Downloaded: 1084

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 orderand sizeof Gare denoted by pand 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 uand vin G, the distance d(u, v) from uto vis defined as the length of a shortest u − vpath in G.The eccentricity e(v) of a vertex vin Gis the maximum distance from vto a vertex of G.The radius rad Gof Gis the minimum eccentricity among the vertices of G,while the diameter diam Gof Gis 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 neighborhoodof a vertex vis the set N(v) consisting of all vertices uwhich are adjacent with v. A vertex vis an extreme vertexif 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 uand vin G, the detour distance D(u, v) from uto vis defined as the length of a longest u − vpath in G.The detour eccentricity eD(v) of a vertex vin Gis the maximum detour distance from vto a vertex of G.The detour radius radDGof Gis the minimum detour eccentricity among the vertices of G,while the detour diameter diamDGof Gis 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.

Advertisement

2. Monophonic distance

Definition 2.1.A chord of a path u1, u2,…, unin a connected graph G is an edge uiujwith j ≥ i +2. A u − v path P is called a monophonic path if it is a chordless path. The length of a longest uv monophonic path is called the monophonic distance from u to v, and it is denoted by dm(u, v). A uv monophonic path with its length equal to dm(u, v) is known as a uv monophonic.

Example 2.2.Consider the graph Ggiven in Figure 1. It is easily verified that d(v1, v4) = 2, D(v1, v4) = 6, and dm(v1, v4) = 4. Thus the monophonic distance is different from both the distance and the detour distance. The monophonic path P: v1, v2, v8, v7, v4 is v1− v4 monophonic while the monophonic path Q: v1, v3, v4 is not v1− v4 monophonic.

Figure 1.

The graphGin Example 2.2.

The usual distance dand the detour distance Dare metrics on the vertex set Vof a connected graph G,whereas the monophonic distance dmis not a metric on V.For the graph Ggiven in Figure 1, dm(v4, v6) = 5, dm(v4, v5) = 1 and dm(v5, v6) = 1. Hence dm(v4, v6) > dm(v4, v5) + dm(v5, v6), 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

0du,vdmu,vDu,vp1.E1

Result 2.4.Let uand vbe any two vertices in a connected graph G. Then

  1. dm(u, v) = 0 if and only if u= v.

  2. dm(u, v) = 1 if and only if uvis an edge of G.

  3. dm(u, v) = p −1 if and only if Gis the path with endvertices uand v.

  4. d(u, v) = dm(u, v) = D(u, v) if and only if Gis a tree.

Definition 2.5.For any vertex v in a connected graph G, the monophonic eccentricity of v is em(v) = max{dm(u, v) : uV}. A vertex u of G such that dm(u, v) = em(v) is called a monophonic eccentric vertex of v. The monophonic radius and monophonic diameter of G are defined by radmG = min{em(v) : vV} and diammG = max{em(v) : vV}, respectively.

Example 2.6.Table 1 shows the monophonic distance between the vertices and also the monophonic eccentricities of vertices of the graph Ggiven in Figure 1. It is to be noted that radmG= 3 and diammG= 5.

dm(vi, vj)v1v2v3v4v5v6v7v8em(v)
v1011414344
v2104315415
v3140124444
v4431015145
v5112101333
v6454510115
v7344131014
v8414431104

Table 1.

Monophonic eccentricities of the vertices of the graph Gin Figure 1.

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 Ggiven in Figure 1, em(v5) = 3 and em(v6) = 5.

Note 2.8.Any two vertices uand vin a tree Tare connected by a unique path, and so d(u, v) = dm(u, v) = D(u, v). Hence rad T= radmT= radDTand diam T= diammT= diamDT.The monophonic radius and the monophonic diameter of some standard graphs are given in Table 2.

Graph GKpCpW1,p−1 (p≥ 4)K1,p−1 (p≥ 2)Km,n(m,n≥ 2)Pp
radmG1p− 2112p2
diammG1p− 2p− 322p− 1

Table 2.

Monophonic radius and monophonic diameter of some standard graphs.

The next theorem follows from Proposition 2.3.

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

  1. e(v) ≤ em(v) ≤ eD(v) for any vertex v in G.

  2. rad G ≤ radmG ≤ radDG.

  3. diam G ≤ diammG ≤ diamDG.

Theorem 2.10.(a) If a, band c are integers with3 ≤ a ≤ b ≤ c, then there exists a connected graph G such that rad G= a, radmG= band radDG= c.

(b) If a, band c are integers with5 ≤ a ≤ b ≤ c, then there exists a connected graph G such that diam G= a, diammG= band diamDG= c.

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

Case (i)3 ≤ a= b= c.Consider G = P2a +1, the path of order 2a+ 1. It is clear that rad G= radm G= radDG= a.

Case (ii)3 ≤ a ≤ b < c.Let F1 : u1, u2,…, ua−1 and F2 : v1, v2,…, va−1 be two copies of the path Pa−1 of order a −1. Let F3 : w1, w2,…, wb−a+3 and F4 : z1, z2,…, zb−a+3 be two copies of the path Pb−a+3 of order b−a+3,and F5 = Kc−b+1 the complete graph of order c − b+ 1 with V(F5) = {x1, x2,…, xc−b+1}. We construct the graph Gas follows: (i) identify the vertices x1 in F5 and w1 in F3; also identify the vertices xc−b+1 in F5 and z1 in F4; (ii) identify the vertices wb−a+3 in F3 and u2 in F1, and identify the vertices zb−a+3 in F4 and v2 in F2; and (iii) join each vertex wi(1 ≤ i ≤ b−a+2) in F3 and u1 in F1, and join each vertex zi(1 ≤ i ≤ b−a+2) in F4 and v1 in F2. The resulting graph Gis shown in Figure 2. It is easily verified that e(v) = aif vV(F5); e(v) > aif vV(G) − V(F5), em(v) = bif vV(F5); em(v) > bif vV(G) − V(F5) and eD(v) = cif vV(F5); and eD(v) > cif vV(G) − V(F5). It follows that rad G = a, radmG= b, and radDG= c.

Figure 2.

A graphGin Case (ii) of Theorem 2.10(a).

Case (iii)3 ≤ a < b= c.Let E1 : v1, v2,…, v2a+1 be a path of order 2a+ 1. Let E2 : u1, u2,…, ub−a+3 and E3w1, w2,…, wb−a+3 be two copies of the path Pb−a+3 of order b − a+ 3, and let Ei(4 ≤ i ≤2(b − a) + 3) be 2(b − a) copies of K1. We construct the graph Gas follows: (i) identify the vertices va+1 in E1, u1 in E2,and w1 in E3; (ii) identify the vertices va−1 in E1 and ub−a+3 in E2, and identify the vertices va+3 in E1 and wb−a+3 in E3; and (iii) join each Ei(4 ≤ i ≤ ba+ 3) with va+1 in E1 and ui−1 in E2, and join each Ei(b − a+ 4 ≤ i ≤2(b − a) + 3) with va+1 in E1 and wi−b+a−1 in E3. The resulting graph Gis shown in Figure 3.

Figure 3.

A graphGin Case (iii) of Theorem 2.10(a).

It is easily verified that e(va+1) = a; e(v) > aif vV(G) {va+1}; em(va+1) = b; em(v) > bif vV(G) {va+1},and eD(va+1) = c; and eD(v) > cif vV(G) {va+1}. It follows that rad G= a, radmG= b, and radDG= c.

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

Case (i)5 ≤ a= b= c.Let Gbe a path of order a+1. Then diam G= diammG= diamDG= a.

Case (ii)5 ≤ a ≤ b < c.Let F1 : u1, u2,…, ua−1 be the path Pa−1 of order a −1; F2 : w1, w2,…, wb−a+3 be the path Pb−a+3 of order b − a+ 3;and F3 = Kc−b+1 be the complete graph of order cb+1 with V (F3) = {x1, x2,…, xc−b+1}. We construct the graph Gas follows: (i) identify the vertices x1 in F3 and w1 in F2, and identify the vertices wb−a+3 in F2 and u2 in F1, and (ii) join each vertex wi(1 ≤ i ≤ ba+ 2) in F2 and u1 in F1. The resulting graph Gis shown in Figure 4. It is easily verified that e(v) = aif v∈ (V(F3) {x1}) {ua−1}; e(v) < aif vV(F2) (V(F1) {ua−1}),and em(v) = bif v∈ (V(F3) {x1})  {ua−1}; em(v) < bif vV(F2) (V(F1) {ua−1}),and eD(v) = cif v∈ (V(F3) {x1}) {ua−1}; and eD(v) < cif vV(F2) (V(F1) {ua−1}). It follows that diam G= a, diammG= band diamDG= c.

Figure 4.

A graphGin Case (ii) of Theorem 2.10(b).

Case (iii)5 ≤ a < b= c.Let E1 : v1, v2,…, va+1 be a path of order a+ 1; E2 : w1, w2,…, wb−a+3 be another path of order ba+ 3; and Ei(3 ≤ i ≤ b − a+ 2) be b − acopies of K1. Let Gbe the graph obtained from Eifor i= 1,2,…, ba+ 2 by identifying the vertices va−2 and vaof E1 with w1 and wb−a+3 of E2, respectively, and joining each Ei(3 ≤ i ≤ ba+ 2) with va−2 and wi. The graph Gis shown in Figure 5.

Figure 5.

A graphGin Case (iii) of Theorem 2.10(b).

It is easily verified that e(v) = aif v∈ {v1, va+1}; e(v) ≤ aif vV(G) {v1, va+1},and em(v) = bif v∈ {v1, va+1}; em(v) ≤ bif vV(G) {v1, va+1},and eD(v) = cif v∈ {v1, va+1}; and eD(v) ≤ cif vV(G) {v1, va+1}. It follows that rad G= a, radmG= band radDG= c.

For any connected graph G, the inequalities rad G ≤ diam G ≤2 rad Gand radDG ≤ diamDG ≤ 2 radDGhold. However, this is not true in the case of monophonic radius and monophonic diameter. For example, when the graph Gis the wheel W1,p−1 (p ≥6),it is easily seen that radmG= 1 and diammG= p −3 3 so that diammG >2 radmG.

It is proved in Ref. [6] that if aand bare any two positive integers such that a ≤ b ≤2a, then there is a connected graph Gwith rad G= aand diam G= b.Also, it is proved in Ref. [35] that if aand bare any two positive integers such that a ≤ b ≤2a, then there is a connected graph Gwith radDG= aand diamDG= b.

Now, the following theorem gives a realization result for radmGdiammG.

Theorem 2.11.If a and b are positive integers with a ≤ b, then there exists a connected graph G such that radmG= a and diammG= b.

Proof.This result is proved by considering three cases.

Case (i)a= b ≥1. Let Gbe the cycle Ca+2. Then radmG= aand diammG= b.

Case (ii)a < b ≤2a.Let C1 : u1, u2,…, ua+2, u1 be a cycle of order a+ 2 and C2 : v1, v2,…, vb−a+2, v1 be a cycle of order b − a+ 2. Let Gbe the graph obtained by identifying the vertex u1 of C1 and v1 of C2. Since b ≤2a,it follows that b − a+ 2 ≤ a+ 2. It is clear that dm(u1, x) ≤ afor any xin Gand dm(u1, ua+1) = a.Therefore, em(u1) = a.Also, it is clear that there is no vertex xwith em(x) < aand so radmG= a.It is clear that dm(u3, v3) = band dm(u3, x) ≤ bfor any vertex xin Gand so em(u3) = b.Also, it is easy to see that em(x) ≤ bfor every vertex xin Gso that diammG= b.

Case (iii)b >2a.Let Gbe the graph obtained by identifying the central vertex of the wheel W= K1 + Cb+2 (b ≥2) and an endvertex of the path P2a. Since b >2a, em(x) = bfor any vertex xV(Cb+2). Also, a ≤ em(x) 2afor any vertex xV(P2a) and em(va) = a.Hence radmG= aand diammG= 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 em(v) = radmG, and the subgraph induced by the monophonic central vertices of G is the monophonic center Cm(G) of G. A vertex v in G is called a monophonic peripheral vertex if em(v) = diammG, and the subgraph induced by the monophonic peripheral vertices of G is the monophonic periphery Pm(G) of G.

Example 2.13.Consider the graph Ggiven in Figure 1. It is easily verified that v5 is the monophonic central vertex and v2, v4, and v6 are the monophonic peripheral vertices of G.

Remark 2.14.The monophonic center of a connected graph neednot be connected. For the graph Ggiven in Figure 6, Cm(G) = {v3, v6}.

Figure 6.

A graphGin Remark 2.14.

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

Proof.Let Gbe a graph. We show that Gis the monophonic center of some graph. Let l= dmbe the monophonic diameter of G. Let P: u1, u2,…, uland Q: v1, v2,…, vlbe two copies of the path Pl. The required graph Hgiven in Figure 7 is got from G, P, and Qby joining each vertex of Gwith u1 in Pand v1 in Q.Then emH(x) = dmfor each vertex xin Gand dm+ 1 ≤ emH(x) 2 dmfor each vertex xnot in G. Therefore, V(G) is the set of monophonic central vertices of Hand so Cm(H) = G.

Figure 7.

A graphHin Theorem 2.15.

More specifically, it is proved in Ref. [43] that the center of every connected graph Glies in a single block of G.Also, it is proved in Ref. [35] that the detour center of every connected graph Glies 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 Cm(G) of every connected graph G is a subgraph of some block of G.

Proof.Suppose that there is a connected graph Gsuch that its monophonic center Cm(G) is not a subgraph of a single block of G.Then Ghas a cut vertex vsuch that G − vcontains two components H1 and H2,each containing vertices of Cm(G). Let ube a vertex of Gsuch that em(v) = dm(u,v), and let P1 be a u − vlongest monophonic path in G.Then at least one of H1 and H2 contains no vertices of P1, say H2 contains no vertex of P1. Now, take a vertex win Cm(G) that belongs to H2, and let P2 be a v − wlongest monophonic path in G.Since vis a cut vertex, P1 followed by P2 gives a u − wlongest monophonic path with its length greater than that of P1. This gives em(w) > em(v) so that wis not a monophonic central vertex of G,which is a contradiction.

Corollary 2.17.For any tree, the monophonic center is isomorphic to K1or K2.

It is proved in Ref. [44] that a nontrivial graph Gis the periphery of some connected graph if and only if every vertex of Ghas eccentricity 1 or no vertex of Ghas eccentricity 1. Also, it is proved in Ref. [35] that a connected graph Gof order p ≥3 and radius 1 is the detour periphery of some connected graph if and only if Gis 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 eccentricity1 or no vertex of G has monophonic eccentricity1.

Definition 2.19.A connected graph G is monophonic self-centered if radmG = diammG, that is, if G is its own monophonic center.

Example 2.20.The complete graph Kn,the cycle Cn, and the complete bipartite graph Km,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 − vdetour monophonic path, we mean a longest u − vmonophonic 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, vS. 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 Ggiven in Figure 8, S1 = {v1, v2, v3}, S2 = {v2, v3, v4}, S3 = {v5, v6, v2}, S4 = {v5, v6, v3}, S5 = {v1, v3, v5}, S6 = {v1, v3, v6}, S7 = {v2, v4, v5}, and S8 = {v2, v4, v6} are the minimum detour monophonic sets of Gand so dm(G) = 3.

Figure 8.

The graphGin Example 3.2.

If a vertex belongs to every minimum detour monophonic set of G, then it is called a detour monophonic vertexof G. If Sis the unique minimum detour monophonic set of G, then Sis 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 Gthat 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 vbe an extreme vertex and let Sbe a detour monophonic set of G. If vis not an element of S, then there exist two elements xand yin Ssuch that vis an internal vertex of an xydetour monophonic path, say P. Let uand wbe the vertices on Padjacent to v. Then uand ware not adjacent and so vis not an extreme vertex of G, which is a contradiction. Therefore vbelongs to every detour monophonic set of G. Thus, if Sis the set of all extreme vertices of G, then dm(G) ≥ |S|. On the other hand, if Sis a detour monophonic set of G, then dm(G) ≤ |S|. Therefore dm(G) = |S| and Sis 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 vand 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 Bis a branch of Gat some cut vertex, it follows Theorem 3.4 and Theorem 3.5 that every minimum detour monophonic set of Gcontains at least one vertex from Bthat 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 Gis not a complete graph. Then there exist two vertices uand vsuch that uand vare not adjacent in G. Since Gis connected, there is a detour monophonic path from uto v, say P, with length at least 2. Clearly, (V(G) − V(P)) {u, v} is a detour monophonic set of Gand hence dm(G) ≤ p− 1, which is a contradiction. Conversely, if Gis 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, yV(G) such that Gcontains an xydetour monophonic path Pof length diammG= d. Let S= (V(G)−V(P)) {x, y}. Since Sis a detour monophonic set of G, it follows that dm(G) ≤ |S| ≤ pd+ 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 Tbe any nontrivial tree. Let P: u= v0, v1,…, vdbe a monophonic diametral path. Let kbe the number of endvertices of Tand let lbe the number of internal vertices of Tother than v1, v2,…, vd−1. Then d− 1 + l+ k= p. By Theorem 3.3 and Theorem 3.5, dm(T) = kand so dm(T) = pdl+ 1. Hence dm(T) = pd+ 1 if and only if l= 0, if and only if all the internal vertices of Tlie on the monophonic diametral path P, and if and only if Tis a caterpillar.

It is known that radmGdiammGfor a connected graph G. It is proved in Ref. [45] that if aand bare any two positive integers such that ab, then there is a connected graph Gwith radmG= aand diammG= b. The same result can also be extended so that the detour monophonic number can be prescribed when radmG< diammG,and for a proof, one may refer to Ref. [47].

Theorem 3.12.For positive integers r, dand n ≥ 4 with r < d, there exists a connected graph G with radmG = r, diammG = dand dm(G) = n.

Problem 3.13.For any three positive integers r, dand n≥ 4 with r= d, does there exist a connected graph Gwith radmG= r, diammG= dand 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 Ggiven in Figure 8. The minimal detour monophonic sets are S1 = {v1, v2, v3}, S2 = {v2, v3, v4}, S3 = {v5, v6, v2}, S4 = {v5, v6, v3}, S5 = {v1, v3, v5}, S6 = {v1, v3, v6}, S7 = {v2, v4, v5}, S8 = {v2, v4, v6} and S9 = {v1, v4, v5, v6}. 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 Ggiven in Figure 8, S9 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 with2 ≤ 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 Gmay contain more than one minimum detour monophonic sets. For example, the graph Ggiven in Figure 8 contains eight minimum detour monophonic sets. For each minimum detour monophonic set Sin G, there is always some subset Tof Sthat uniquely determines Sas 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 inFigure 9, S1 = {z, w, v}, S2 = {z, w, u} and S3 = {z, w, x} are the minimum detour monophonic sets of G. It is clear that fdm(S1) = 1, fdm(S2) = 1 and fdm(S3) = 1 so that fdm(G) = 1. For the graph G given inFigure 10, S= {y, v} is the unique minimum detour monophonic set of G and so fdm(G) = 0.

Figure 9.

A graphGwith fdm(G) = 1.

Figure 10.

A graphGwithfdm(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 Gfor 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

  1. fdm(G) = 0 if and only if G contains exactly one minimum detour monophonic set.

  2. 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.

  3. 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 with0 ≤ 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 Sxof 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 Sx. The x-detour monophonic number of G, denoted by dmx(G), is defined to be the minimum cardinality of an x-detour monophonic set of G. An x-detour monophonic set of cardinality dmx(G) is called a dmx-set of G.

It is easy to observe that for any vertex xin G, xdoes not belong to any dmx-set of G.

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

Figure 11.

The graphGin Example 4.2.

VertexMinimum vertex detour monophonic setsVertex 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

Table 3.

Vertex detour monophonic numbers of the graph Gin Figure 11.

The next two theorems are easy to prove.

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

  1. Every dmx-set of G contains all its extreme vertices other than the vertex x(whether x is extreme vertex or not).

  2. No dmx-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 ≤ dmx(G) ≤ p− 1.

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

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

Corollary 4.6.A graph G is complete if and only if dmx(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 Sxis called a minimal x-detour monophonic set if no proper subset of Sxis 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 dmx+(G).

Example 4.8. For the graph Ggiven 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.

Figure 12.

The graphGin Example 4.8.

Vertex xMinimum x-detour monophonic setsdmx(G)Minimal x-detour monophonic setsdmx+(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

Table 4.

Upper vertex detour monophonic numbers of the graph Gin Figure 12.

Since every minimum x-detour monophonic set is a minimal x-detour monophonic set, we have 1 ≤ dmx(G) ≤ dmx+(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 dmx(G) = 1, then dmx+(G) ≤ p − 2.

Theorem 4.10.Let x be any vertex in a connected graph G. Then dmx(G) = p− 1 if and only if dmx+(G) = p− 1.

Theorem 4.11.For any four integers j, k, l and p with2 ≤ jklp− 7, there exists a connected graph G of order p with dmx(G) = j, dmx+(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 Gand let Sxbe a minimum x-detour monophonic set of G. A subset S′ of Sxis an x-forcing subset for Sxif Sxis the unique minimum x-detour monophonic set that contains S′. An x-forcing subset for Sxof minimum cardinality is a minimum x-forcing subset of Sx. The cardinality of a minimum x-forcing subset of Sxis the forcing x-detour monophonic number fdmx(Sx) in G. The forcing x-detour monophonic number of G is fdmx(G) = min { fdmx(Sx)}, where the minimum is taken over all minimum x-detour monophonic sets Sxin G.

Definition 4.13.Let x be any vertex of a connected graph G. The upper forcing x-detour monophonic number, fdmx+(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 Ggiven 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.

Figure 13.

The graphGin Example 4.14.

Vertex xdmx-setsdmx(G)x-forcing subsetsfdmx(G)fdmx+(G)
t{v,w}, {y,z}, {w,y}2{v}, {z}, {w,y}12
u{t,v,w}, {t,y,z}, {t,w,y}3{v}, {z}, {w,y}12
v{t,z}2Φ00
w{t,v}, {t,z}2{v}, {z}11
y{t,v}, {t,z}2{v}, {z}11
z{t,v}2Φ00

Table 5.

Forcing and upper forcing vertex detour monophonic numbers of the graph Gin Figure 13.

Theorem 4.15.For any vertex x in a connected graph G,0 ≤ fdmx(G) ≤ fdmx+(G) ≤ dmx(G).

The following theorem gives a realization result for the parameters fdmx(G), fdmx+(G), dmx(G), and for a proof, one may refer to Ref. [52].

Theorem 4.16.For any three integers r, s and t with2 ≤ rstwith 2rs≥ 0, there exists a connected graph G with fdmx(G) = r, fdmx+(G) = sand dmx(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.

© 2017 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

P. Titus and A.P. Santhakumaran (December 20th 2017). Monophonic Distance in Graphs, Graph Theory - Advanced Algorithms and Applications, Beril Sirmacek, IntechOpen, DOI: 10.5772/intechopen.68668. Available from:

chapter statistics

1084total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Spectra and Quantum Transport on Graphs

By Victor Chulaevsky

Related Book

First chapter

Introductory Chapter: Traveling Salesman Problem - An Overview

By Donald Davendra and Magdalena Bialic-Davendra

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us