On Restricted Detour Median of Special Graphs

Abstract

The restricted detour distance between two vertices is the length of longest path $P$ such that the induced subgraph for a vertex set of $P$ is identical $P$. The number of restricted detour distance of a vertex $v$ of a connected graph $Ǥ$ is a summation of restricted detour distances from $v$ to all vertices of $Ǥ$. In this paper, we give a new definitions called restricted detour median graph (RDM-graph) and restricted detour self-median graph (RDSM-graph) and then we find many results related with them.

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

1. Introduction

There are many types of distance in a simple connected graph $Ǥ$ in graph theory [1, 2], some of them depend on distance between two vertices from the set vertex of $Ǥ$, $VǤ$, such as ordinary distance [3], detour distance and restricted detour distance [4, 5], and Steiner distance [6], while others depend on two subsets of $VǤ$, such as maximum (or average or minimum) distance between two subsets of $VǤ$ [7], sometimes depends on one vertex and a subset of $VǤ$ such as min $-k-$distance and max $-k-$distance, where $k$ does not exceed the number of vertices of the graph [8], in addition to the presence of a invariant number that depends on degrees [9] only or depends on the ordinary distance and degrees [10, 11]. The reason for the diversity of finding definitions of distance in graph theory is because of its very great importance of applications, such as geometric communications [12], computer science [13], and chemistry science [14]. For any two vertices, $u$ and $v$, the shortest path is the ordinary distance, denoted by $du,v$. The longest path between two distinct vertices, $u$ and $v$, is the detour distance, $d_{D}u,v$, but the restricted detour distance $d_{Ǥ}^{\mathrm{\ast }}u,v$ is the longest path $P$ that connected two vertices $u$ and $v$ such that $<VP>=P$, where $<VP>$ reference to a subgraph of $Ǥ$ that is induced by $VP$ where $VP$ is its vertex set; furthermore, if an edge of $Ǥ$ connects two vertices of $VP$, then it is an edge of $<VP>$ [15]. The topics of detour distance and restricted detour distance have been the subject of numerous recent studies; you can see them in references [16–18]. Therefore, our aim in this paper is to present a new concept related with restricted detour number.

Definition 1.

For any connected graph $Ǥ$, the restricted detour distance [4] of the vertex $v\in VǤ$ is$$\begin{array}{}\text{(1)}& d_{Ǥ}^{\mathrm{\ast }}v={\displaystyle \sum }_{u\in VǤ}{d}^{\mathrm{\ast }}u,v.\end{array}$$

Definition 2.

The restricted detour median graph (RDM-graph) for all connected graph $Ǥ$ is a subgraph $M^{\mathrm{\ast }}Ǥ$ of a graph $Ǥ$ that is induced from those vertices which have minimum number of restricted detour distance.

The importance of RDM-graph is that we can obtain a new chemical compound from a given chemical compound that is more stable and clearer in terms of some of the chemical properties of the chemical compounds, for example, boiling point or melting point.

It is unknown whether for every a connected graph $Ǥ$, there exists a graph $H$ such that $M^{\mathrm{\ast }}H=Ǥ$. For any connected graph $Ǥ$ and every vertex $u$ that does not belong to the set of vertex of $Ǥ$, we note that $d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}v>d_{Ǥ}^{\mathrm{\ast }}v$, $\forall v\in VǤ$, where ${Ǥ}^{\prime }$ is got from $Ǥ$ by joining $u$ to at last one vertex of $Ǥ$. To illustrate this, we provide the next example.

Example 1.

Consider a graph $Ǥ$ that appears in Figure 1.

[figure(s) omitted; refer to PDF]

Definition 3.

For any connected graph $Ǥ$, if $M^{\mathrm{\ast }}Ǥ=Ǥ$, then $Ǥ$ is called a restricted detour self-median graph (RDSM-graph).

Example 2.

The graphs $C_p,K_{ᶆ,ᶆ}$, and $K_p$ are RDSM-graphs, $p,ᶆ\ge 3$.

It is very difficult to find graph $H$ such that $M^{\mathrm{\ast }}H=H\supset Ǥ$.

Definition 4.

The graph which has $p$ of vertices and without edges is called an empty graph, which is denoted as $E_p$ [2].

Definition 5.

Let $Ǥ$ be a simple connected graph of order $p$ which has the vertex set $VǤ=u_1,u_2,\dots ,u_p$ and $T=t_1,t_2,\dots ,t_p$ be an $n$-tuple of nonnegative integers. The thorn graph ${Ǥ}^{t_p}$ is a graph generated by joining $t_i$ vertices of degree one to the vertex $u_i\in VǤ$, $i=1,2,\dots ,p$ [19].

2. RDM-Graph Containing Some Special Graphs

In this section, we find RDM-graph for some special graphs, such as complete bipartite, path, and cycle graphs.

2.1. Complete Bipartite Graph

If $Ǥ\equiv K_{\mathbf{ᶆ},\mathbf{ᶇ}},ᶆ,ᶇ\ge 2$ and $ᶆ\ne ᶇ,$ say $ᶆ>ᶇ$, then there is graph $H\equiv K_{ᶆ,ᶆ}$, which is a RDM-graph containing induced subgraph $K_{ᶆ,ᶇ}$, that is, $M^{\mathrm{\ast }}{K}_{ᶆ,ᶆ}\supset K_{ᶆ,ᶇ}$, see Figure 2.

[figure(s) omitted; refer to PDF]

Moreover, for $K_{{ᶇ}_1,{ᶇ}_2,{ᶇ}_3,\dots ,{ᶇ}_t}\equiv K_{ᶇt}$, ${ᶇ}_i=ᶇ$, $i=1,2,\dots ,t$, we have $d_{K_{ᶇt}}^{\mathrm{\ast }}v=ᶇt+1-2$, for each $v$ in $V{K}_{ᶇt}$; thus, $K_{ᶇt}$ isa RDM-graph for itself. Consider $K_{ᶆ,ᶇ,t}$, with $ᶆ,ᶇ,t$ not equal integers without loss of generality, and we assume $ᶆ>ᶇ\ge t$. One may check that $K_{ᶆ,ᶇ,t}$ is an induced subgraph of $K_{ᶆ,ᶆ,ᶆ}$, which is a restricted detour median itself. Thus, in general, $K_{{ᶇ}_1,{ᶇ}_2,{ᶇ}_3,\dots ,{ᶇ}_t}$ is an induced subgraph of self-RDM-graph $K_{ᶇt}$, where $ᶇ=\max {ᶇ}_1,{ᶇ}_2,{ᶇ}_3,\dots ,{ᶇ}_t$.

Proposition 1.

If the empty graph $Ǥ$ of order $ᶇ$ has a vertex set $u_1,u_2,\dots ,u_{ᶇ}$, $ᶇ>1$, then $Ǥ$ is a RDM-graph of a graph $K_{ᶆ,ᶇ}$, for $ᶆ>ᶇ$.

Proof 1.

In $K_{ᶆ,ᶇ}$, we have$$\begin{array}{c}\text{(2)}& d_{K_{ᶆ,ᶇ}}^{\mathrm{\ast }}{u}_i=ᶆ+2ᶇ-1=ᶆ+ᶇ-2+p,i=1,2,\dots ,ᶇ.d_{K_{ᶆ,p}}^{\mathrm{\ast }}{v}_j=ᶇ+2ᶆ-1=ᶆ+ᶇ-2+ᶆ,j=1,2,\dots ,ᶆ.\\ \because ᶆ>ᶇ,\text{\hspace{0.17em}then\hspace{0.17em}}{M}^{\mathrm{\ast }}{K}_{ᶆ,ᶇ}=Ǥ=<u_1,u_2,\dots ,u_{ᶇ}>.\end{array}$$

2.2. Path Graph

We shall give some examples for special path graphs $P_p$ such that there exits a graph $H$, with a path $P_p$ as an induced subgraph of $H$, and $M^{\mathrm{\ast }}H=P_p$ for some $p$.

If ${Ǥ=P}_1$, ($Ǥ$ is a trivial graph), then $H_1$ is a hand fan graph, where $\alpha =d_{Ǥ}^{\mathrm{\ast }}{u}_i={\sum }_{v\in V{H}_1-u_i}{d}^{\mathrm{\ast }}{u}_i,v=2+p/2p-3=pp-3+4/2$, for $i=1,2,\dots ,p-1$, see Figure 3.$$\begin{array}{}\text{(3)}& \therefore M^{\mathrm{\ast }}{H}_1{=P}_1.\end{array}$$

1. If $Ǥ=P_2$, then $H_2$ is a graph as illustrated in Figure 4.$$\begin{array}{}\text{(4)}& \therefore M^{\mathrm{\ast }}{H}_2=P_2.\end{array}$$

2. If $Ǥ=P_3:u_1,u_2,u_3$, one may easily check that restricted detour distance for each vertex of $H_3$ in Figure 5 shown in the following.

  Thus, $M^{\mathrm{\ast }}{H}_3=P_3$.

3. If $Ǥ=P_4:u_1,u_2,u_3,u_4$, then $H_4$ is shown in Figure 6, and the depicted graph satisfies $M^{\mathrm{\ast }}{H}_4=P_4$.

4. If $Ǥ=P_5:u_1,u_2,u_3,u_4,u_5$, then $M^{\mathrm{\ast }}{H}_5=P_5$, where $H_5$ is illustrated in Figure 7.

[figure(s) omitted; refer to PDF]

Finally, we think that, there exists a graph $H$ for every path $P_p$, $p\ge 6$, containing $P_p$ as induced subgraph such that $M^{\mathrm{\ast }}H=P_p$.

Problem 1.

How to describe the construction of such $H$?

2.3. Cycle Graph

In this subsection, we got some results through which we were able to obtain thorn cycle graph $H=C_p^t$ at $t=1$ from $Ǥ$ that resulted from adding vertices and creating edges between the added vertices and the vertices of $Ǥ$ such that $M^{\mathrm{\ast }}H=C_p$, $p\ge 4$.

1. If $Ǥ=C_3:u_1,u_2,u_3,u_1$, then $H_6$ in Figure 8 satisfies $M^{\mathrm{\ast }}{H}_6=C_3$.

2. If $Ǥ=C_4:u_1,u_2,u_3,u_4,u_1$, then $H_7$ in Figure 9 satisfies $M^{\mathrm{\ast }}{H}_7=C_4$.

[figure(s) omitted; refer to PDF]

Theorem 1.

For any cycle $C_p{:u}_1,u_2,u_3,{\dots ,u}_p,u_1$, $p\ge 4$, there exists a graph $H$ in which $C_p$ is an induced subgraph of $H$ and $M^{\mathrm{\ast }}H=C_p$.

Proof 2 (see Figure 10).

The following cases is clear for $i=1,2,3,\dots ,p.$

[figure(s) omitted; refer to PDF]

Case 1.

If $p$ is even, then$$\begin{array}{}\text{(5)}& d_H^{\mathrm{\ast }}{u}_i=1+2{\displaystyle \sum }_{i=1}^{p/2-1}i+\frac{p}{2}+2{\displaystyle \sum }_{i=2}^{p/2}i+\frac{p}{2}+1=4{\displaystyle \sum }_{i=1}^{p/2}i=\frac{pp+2}{2}.\end{array}$$

Also,$$\begin{array}{}\text{(6)}& d_H^{\mathrm{\ast }}{v}_i=1+2{\displaystyle \sum }_{i=2}^{p/2}i+\frac{p}{2}+1+2{\displaystyle \sum }_{i=3}^{p/2+1}i+\frac{p}{2}+2=4{\displaystyle \sum }_{i=1}^{p/2+1}i-6=\frac{p+2p+4}{2}-6.\end{array}$$

Hence, $M^{\mathrm{\ast }}H=C_p=<u_1,u_2,u_3,{\dots ,u}_p>$.

Case 2.

If $p$ is odd, then$$\begin{array}{}\text{(7)}& d_H^{\mathrm{\ast }}{u}_i=1+2{\displaystyle \sum }_{i=1}^{p-1/2}i+2{\displaystyle \sum }_{i=2}^{p+1/2}i=4{\displaystyle \sum }_{i=1}^{p-1/2}i+p=\frac{1}{2}{p}^2+2p-1.\end{array}$$

Also,$$\begin{array}{}\text{(8)}& d_H^{\mathrm{\ast }}{v}_i=1+2{\displaystyle \sum }_{i=2}^{p+1/2}i+2{\displaystyle \sum }_{i=3}^{p+3/2}i=4{\displaystyle \sum }_{i=1}^{p+1/2}i+p-4=\frac{1}{2}{p}^2+6p-5.\end{array}$$

Hence, $M^{\mathrm{\ast }}H=C_p=<u_1,u_2,u_3,{\dots ,u}_p>$.

From (5) (or (7)) and (6) (or (8)), we note that ${d_H^{\mathrm{\ast }}{v}_i=d}_H^{\mathrm{\ast }}{u}_i+2p-1$.

Proposition 2.

For all connected graph $Ǥ$ of order $p$, $p\le 3$, there exists a graph $H_i$ in which $M^{\mathrm{\ast }}{H}_i=Ǥ$ and $Ǥ$ is an induced subgraph of $H_i$, where $i=1,2,3,4$.

Proof 3.

For $p=1$, we have $H_1=P_3$.

For $p=2$, we have $H_2=P_4$.

For $p=3$, we have $H_3$ and $H_4$ as shown in Figure 11.

[figure(s) omitted; refer to PDF]

Hence, the proof is complete.

Proposition 3.

For any connected graph ${Ǥ}_i$ which has the order $p=4$, ${Ǥ}_i\ne S_4$ (star graph of order 4), there exists a graph $H_i$ such that ${Ǥ}_i$ is an induced subgraph of $H_i$ and $M^{\mathrm{\ast }}{H}_i=H_i$, where $i=1,2,3,4,5$.

Proof 4.

For $p=4$, the corresponding $H_i$ such that $M^{\mathrm{\ast }}{H}_i={Ǥ}_i,i=1,2,3,4,5$ is shown in Figure 12.

Hence, the proof is complete.

[figure(s) omitted; refer to PDF]

3. RDSM-Graph Containing Some Special Graphs

Proposition 4.

Suppose that $Ǥ$ is a RDSM-graph with $VǤ=p$ and $VǤ=u_1,u_2,\dots ,u_p$ Then, there exists a graph $H$ of order $2p$ constructed from $Ǥ$ by adding vertices $v_1,v_2,\dots ,v_p$ with edges $v_i{u}_i:i=1,2,\dots ,p$, and $Ǥ$ is the induced subgraph of $H$ and $M^{\mathrm{\ast }}H=Ǥ$.

Proof 5.

From Figure 13(a), one may easily notice that for all $i=1,2,\dots ,p,$$d_H^{\mathrm{\ast }}{u}_i=2s+p$ and $d_H^{\mathrm{\ast }}{v}_i=2s+3p-2$, in which $s=d_{Ǥ}^{\mathrm{\ast }}{u}_i,i=1,2,\dots ,p$.

[figure(s) omitted; refer to PDF]

Thus, $Ǥ$ is the detour median of $H$, and $Ǥ$ is the induced subgraph of $H$.

The special graphs $K_p,K_{ᶆ,ᶆ}$, and $C_p$ are the graphs satisfying the property mentioned in Proposition 4, $M^{\mathrm{\ast }}H=Ǥ$.

Proposition 5.

If $Ǥ$ is an RDSM-graph of order $p$, $p\ge 3$, then $Ǥ$ contains no end-vertex.

Proof 6.

If $v$ is a vertex has degree one, and $u$ is the unique vertex adjacent to $v$, then$$\begin{array}{c}\text{(9)}& d_{Ǥ}^{\mathrm{\ast }}v=p-1+d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}u,\text{\hspace{0.17em}where\hspace{0.17em}}{Ǥ}^{\prime }=Ǥ-v.=p-1+d_{Ǥ}^{\mathrm{\ast }}u-1\\ =d_{Ǥ}^{\mathrm{\ast }}u+p-2>d_{Ǥ}^{\mathrm{\ast }}u.\end{array}$$

Thus, $v\notin M^{\mathrm{\ast }}Ǥ$ contradicting $M^{\mathrm{\ast }}Ǥ=Ǥ$.

Proposition 6.

Suppose that $Ǥ$ is a connected RDSM-graph where $VǤ=p$, $p>4$, and $v$ is an end-vertex of $G$, then $v\notin M^{\mathrm{\ast }}Ǥ$.

Proof 7.

By contradiction (see Figure 13).

Let $u$ be the vertex adjacent to $v$ in $Ǥ$, and let ${Ǥ}^{\prime }=Ǥ-v$.$$\begin{array}{}\text{(10)}& \text{Clearly},d_{Ǥ}^{\mathrm{\ast }}v=d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}u+p,\text{\hspace{0.17em}since\hspace{0.17em}}{d}_{Ǥ}^{\mathrm{\ast }}u=1+d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}u.\end{array}$$

Thus, $d_{Ǥ}^{\mathrm{\ast }}v=d_{Ǥ}^{\mathrm{\ast }}u+p-1,p\ge 4$.

Therefore, $d_{Ǥ}^{\mathrm{\ast }}v>d_{Ǥ}^{\mathrm{\ast }}u$.

By the definition of the median vertex, $v\notin M^{\mathrm{\ast }}Ǥ$.

Corollary 1.

If $u$ is a median vertex in $Ǥ$, then $u$ is the only median vertex in $Y$.

Proof 8.

Let $w\in V{Ǥ}^{\prime }$, then from Figure 13, we obtain$$\begin{array}{}\text{(11)}& d_{Ǥ}^{\mathrm{\ast }}w=d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}w+d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}w,u+1.\end{array}$$

If $u\in M^{\mathrm{\ast }}{Ǥ}^{\prime }$, then $d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}w\ge d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}u$.

From (10), we have $d_{Ǥ}^{\mathrm{\ast }}w\ge d_{Ǥ}^{\mathrm{\ast }}u+1+d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}w,u$.

From (11), we have $d_{Ǥ}^{\mathrm{\ast }}w\ge d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}u+1+d_{{Ǥ}^{\prime }}^{\mathrm{\ast }}w,u$.

Hence, if $w\ne u$, then $d_{Ǥ}^{\mathrm{\ast }}w>d_{Ǥ}^{\mathrm{\ast }}u$, which implies that $u$ is the only median vertex in $Y$.

To explain the previous propositions, we take the following examples:

Example 3.

Let $C_{2ᶇ}:u_1,u_2,\dots ,u_{2ᶇ-1},u_{2ᶇ},u_1$, $ᶇ\in N-1$ and $v$ is an isolated vertex, then the graph $Ǥ$ is constructed from $C_{2ᶇ}$ with edge ${vu}_1$.

It is easy to calculate$$\begin{array}{c}\text{(12)}& d_{C_{2ᶇ}}^{\mathrm{\ast }}{u}_1=2+2{\displaystyle \sum }_{i=ᶇ+1}^{2ᶇ-2}i+ᶇ=3{ᶇ}^2-6ᶇ+4,d_{Ǥ}^{\mathrm{\ast }}v=1+2+2+2{\displaystyle \sum }_{i=1}^{ᶇ-2}2ᶇ-i+ᶇ+1=3{ᶇ}^2-4ᶇ+4,\\ d_{Ǥ}^{\mathrm{\ast }}v=d_{Ǥ}^{\mathrm{\ast }}{u}_1+2ᶇ-1,\text{\hspace{0.17em}since\hspace{0.17em}}{d}_{Ǥ}^{\mathrm{\ast }}{u}_1=d_{C_{2ᶇ}}^{\mathrm{\ast }}{u}_1+1,\text{\hspace{0.17em}then}\\ d_{Ǥ}^{\mathrm{\ast }}v=1+d_{C_{2ᶇ}}^{\mathrm{\ast }}{u}_1+2ᶇ-1=d_{C_{2ᶇ}}^{\mathrm{\ast }}{u}_1+2ᶇ.\end{array}$$

$\text{Hence},d_{Ǥ}^{\mathrm{\ast }}{u}_j=d_{c_{2ᶇ}}^{\mathrm{\ast }}{u}_j+d_{c_{2ᶇ}}^{\mathrm{\ast }}{u}_1,u_j+1,j>1.$

Since $C_{2ᶇ}$ is a RDSM-graph, then $d_{c_{2ᶇ}}^{\mathrm{\ast }}{u}_i$, for $i=1,2,\dots ,2ᶇ$, is of the value, say N; therefore, $d_{Ǥ}^{\mathrm{\ast }}{u}_1=N+1$,$$\begin{array}{c}\text{(13)}& d_{Ǥ}^{\mathrm{\ast }}{u}_j=N+1+d_{c_{2ᶇ}}^{\mathrm{\ast }}{u}_1,u_j,i=2,3,\dots ,2ᶇ,d_{Ǥ}^{\mathrm{\ast }}v=N+2ᶇ,\text{\hspace{0.17em}hence\hspace{0.17em}}{M}^{\mathrm{\ast }}Ǥ=u_1,\text{\hspace{0.17em}and\hspace{0.17em}so\hspace{0.17em}}v\notin M^{\mathrm{\ast }}Ǥ.\end{array}$$

Example 4.

Let $C_{2ᶇ+1}:u_1,u_2,\dots ,u_{2ᶇ-1},u_{2ᶇ},u_{2ᶇ+1},u_1$, $ᶇ\in N-1$, and $v$ is an isolated vertex, then the graph $Ǥ$ constructed from $C_{2ᶇ+1}$ with edge ${vu}_1$.

As in the previous example, we calculate$$\begin{array}{c}\text{(14)}& d_{C_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1=2+2{\displaystyle \sum }_{i=ᶇ+1}^{2ᶇ-1}i=3ᶇᶇ-1+2,d_{Ǥ}^{\mathrm{\ast }}v=1+2+2+2{\displaystyle \sum }_{i=1}^{ᶇ-1}2ᶇ+1-i=3{ᶇ}^2-ᶇ+3,\\ d_{Ǥ}^{\mathrm{\ast }}v=d_{Ǥ}^{\mathrm{\ast }}{u}_1+2ᶇ+1,\text{\hspace{0.17em}since\hspace{0.17em}}{d}_{Ǥ}^{\mathrm{\ast }}{u}_1=d_{C_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1+1,\text{\hspace{0.17em}then}\\ d_{Ǥ}^{\mathrm{\ast }}v=1+d_{C_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1+2ᶇ+1=d_{C_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1+2ᶇ+2.\end{array}$$

Hence, $d_{Ǥ}^{\mathrm{\ast }}{u}_j=d_{c_{2ᶇ+1}}^{\mathrm{\ast }}{u}_j+d_{c_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1,u_j+1$, $j>1$.

Since $C_{2ᶇ+1}$ is a RDSM-graph, then there is a value $N$ such that $$\begin{array}{c}\text{(15)}& d_{c_{2ᶇ+1}}^{\mathrm{\ast }}{u}_i=N,i=1,2,\dots ,2ᶇ+1,\text{\hspace{0.17em}we\hspace{0.17em}consider\hspace{0.17em}}{d}_{Ǥ}^{\mathrm{\ast }}{u}_1=N+1,d_{Ǥ}^{\mathrm{\ast }}{u}_j=N+1+d_{c_{2ᶇ+1}}^{\mathrm{\ast }}{u}_1,u_j,i=2,3,\dots ,2ᶇ+1,\\ d_{Ǥ}^{\mathrm{\ast }}v=N+2ᶇ+1,\text{\hspace{0.17em}hence\hspace{0.17em}}{M}^{\mathrm{\ast }}Ǥ=u_1,\text{\hspace{0.17em}and\hspace{0.17em}so\hspace{0.17em}}v\notin M^{\mathrm{\ast }}Ǥ.\end{array}$$

To illustrate the above two examples in Figure 14, we take the cycle graph $C_p$ of different orders.

[figure(s) omitted; refer to PDF]

Example 5.

1. For $S_4$, we have a RDSM-graph Q in Figure 15(a), containing $S_4$ as induced subgraph, but $S_4\subset M^{\mathrm{\ast }}Q$, $S_4\ne M^{\mathrm{\ast }}Q$.

2. The Peterson graph, shown in the following is restricted detour self-median, with the number of restricted detour distance of each vertex is 27, see Figure 15(b).

[figure(s) omitted; refer to PDF]

Moreover, the cubic graph of order 8 has for each vertex $v$, see Figure 15(c), $d^{\mathrm{\ast }}v=3+4+4+3+3=17$. We notice that not every cubic graph is a RDSM-graph.

3. For empty graph $E_p$ of order $p$, we have $K_{p,p+1}$

It is obvious that$$\begin{array}{c}\text{(16)}& d^{\mathrm{\ast }}{v}_i=p+1+2p-1=3p-1,i=1,2,\dots ,p,d^{\mathrm{\ast }}{u}_j=p+2p=3p,j=1,2,\dots ,p+1.\end{array}$$

Therefore, $M^{\mathrm{\ast }}{K}_{p,p+1}=E_p$, see Figure 16.

4. For the graph $g_p^{\prime }$ even order $p$ with exactly $p/2$ nonadjacent edge $v_1{v}_2,v_3{v}_4,\dots ,v_{p-1}{v}_p$, $p\ge 4$. We have graph $K_{p,p+1}^{\mathrm{\ast }}$ which is illustrated in Figure 17.

[figure(s) omitted; refer to PDF]

From Figure 17, we note that$$\begin{array}{c}\text{(17)}& d^{\mathrm{\ast }}{v}_i=p+1+1+2p-1=3p-2,\text{\hspace{1em}for\hspace{0.17em}}i=1,2,\dots ,p,d^{\mathrm{\ast }}{u}_i=p+2p=3p,\text{\hspace{0.17em}therefore\hspace{0.17em}}{M}^{\mathrm{\ast }}{K}_{p,p+1}^{\mathrm{\ast }}=g_p^{\prime }.\end{array}$$

Remark 1.

For disconnected graph ${Ǥ}^{″}$ of order 3 and an edge $v_1{v}_2$, we have a graph $H^{″}$ as shown in Figure 18; it is clear that ${Ǥ}^{″}$ is an induced subgraph of $H^{″}$ and $M^{\mathrm{\ast }}{H}^{″}={Ǥ}^{″}$ because $d^{\mathrm{\ast }}{v}_i=7$, $d^{\mathrm{\ast }}{u}_1=9$ for $i=1,2,3$ and $d^{\mathrm{\ast }}{u}_4=8$

[figure(s) omitted; refer to PDF]

Now, consider a disconnected graph $Ǥ$ of $ᶇ$ nonadjacent edges and $ᶆ$ isolated vertices. Let $p=ᶆ+2ᶇ$. Take $H^{\mathrm{\ast }}$ as $K_{p,p+1}^{\mathrm{\ast }}$ with $ᶇ$ nonadjacent edges $v_1{v}_2,v_3{v}_4,\dots ,v_{2ᶇ-1}{v}_{2ᶇ},$ and $ᶆ$ as removed edges $v_{2ᶇ+1}{u}_{2ᶇ+2},v_{2ᶇ+2}{u}_{2ᶇ+3},\dots ,v_{2ᶇ+ᶆ}{u}_{2ᶇ+ᶆ+1},$ which is shown in Figure 19.$$\begin{array}{c}\text{(18)}& d^{\mathrm{\ast }}{v}_i=\begin{array}{cc}p+2+2p-2=3p-2,& \text{for\hspace{0.17em}}i=1,2,\dots ,2ᶇ;\\ p+1-1+2p-1=3p-2,& \text{for\hspace{0.17em}}i=2ᶇ+1,\dots ,2ᶇ+ᶆ,\end{array}{d}^{\mathrm{\ast }}{u}_i=\begin{array}{cc}p+2p=3p,& \text{for\hspace{0.17em}}i=1,2,\dots ,2ᶇ+1;\\ p+1+2p=3p-1,& \text{for\hspace{0.17em}}i=2ᶇ+2,\dots ,2ᶇ+ᶆ+1.\end{array}\end{array}$$

[figure(s) omitted; refer to PDF]

Therefore, $Ǥ$ is an induced subgraph of $H$ and $M^{\mathrm{\ast }}{H}^{\mathrm{\ast }}=Ǥ$.

4. Conclusions

In this article, a new definition “RDM-graph” was presented, which through it is possible to obtain new graphs that is more relevant and consistent, which allows us to find new properties that can be described as an application for some chemical compounds that need bonding between their atoms in order to be more stable.

Author Contributions

All the authors have equally contributed to the final manuscript.

Funding

No funding was received for this paper.

Acknowledgments

This paper was conducted at the College of Computer Science and Mathematics, University of Mosul, Iraq, and the General Directorate of Education in Nineveh, Iraqi Ministry of Education-Mosul, Iraq.

References

[1] F. Buckley, F. Harary, Distance in Graphs, 1990.

[2] G. Chartrand, L. Lesniak, Graphs and Digraphs, 2016.

[3] G. Wayne, R. O. Ortrud, "Distance in Graphs," Structual Analysis of Complex Networks, pp. 49-72, DOI: 10.1007/978-0-8176-4789-6_3, 2010.

[4] G. Chartrand, G. L. Johns, S. Tian, "Detour Distance in Graphs," Annals of Discrete Mathematics, vol. no. 55, pp. 127-136, DOI: 10.1016/S0167-5060(08)70381-9, 1993.

[5] O. A. Herish, D. A. Ivan, "The Restricted Detour Polynomial of the Theta Graph," Al-Rafidain Journal of Computer Sciences and Mathematics, vol. 14 no. No.1, pp. 13-20, DOI: 10.33899/CSMJ.2020.164664, 2020.

[6] P. Dankelmann, W. Goddard, M. A. Henning, H. C. Swart, "Generalized Eccentricity, Radius, and Diameter in Graphs," Networks, vol. 34 no. 4, pp. 312-319, DOI: 10.1002/(SICI)1097-0037(199912)34:4%253C312::AID-NET11%253E3.0.CO;2-V, 1999.

[7] J. Caceres, A. Marquez, M. l. Puertas, "Steiner Distance and Convexity in Graphs," European Journal of Combinatorics, vol. 29 no. 3, pp. 726-736, DOI: 10.1016/j.ejc.2007.03.007, 2008.

[8] R. Mustafa, A. M. Ali, A. M. Khidhir, "M_n–Polynomials of Some Special Graphs," Iraqi Journal of Science, vol. 62 no. 6, pp. 1986-1993, DOI: 10.24996/ijs.2021.62.6.24, 2021.

[9] K. B. Rasool, P. A. Rashed, A. M. Ali, "Relations Between Vertex–Edge Degree Based Topological Indices and Mve-Polynomial of r−Regular Simple Graph," European Journal of Pure and Applied Mathematics, vol. 16 no. 2, pp. 773-783, DOI: 10.29020/nybg.ejpam.v16i2.4698, 2023.

[10] E. A. Najm, A. M. Ali, "Some Properties of Generalized Schultz and Generalized Modified Schultz Distances," Palestine Journal of Mathematics, vol. 13 no. 4, pp. 921-933, 2024.

[11] E. A. Najm, A. M. Ali, "Generalized Schultz and Modified Schultz Polynomials for Some Special Graphs," Iraqi Journal of Science, vol. 65 no. 1, pp. 271-279, DOI: 10.24996/ijs.2024.65.1.23, 2024.

[12] A. M. Khidhir, A. M. Ali, S. M. Aziz, "Application of Width Distance on Semi–Star Link Satellite Constellation," Journal of Discrete Mathematical Sciences and Cryptography, vol. 24 no. 3, pp. 797-807, DOI: 10.1080/09720529.2020.1843265, 2021.

[13] A. Elumalai, "Graph Theory Applications in Computer Science and Engineering," Malaya Journal of Matematik, vol. no. 2, pp. 4025-4027, DOI: 10.26637/MJM0S20/1043, 2020.

[14] N. M. Haithm, D. S. Hanadi, M. A. Ahmed, "Zagreb Indices for Chains of Identically Hexagonal Cycles," Palestine Journal of Mathematics, vol. 12 no. 1, pp. 147-157, 2023.

[15] Z. Chen, M. Dehmer, Y. Shi, "A Note on Distance-Based Graph Entropies," Entropy, vol. 16 no. 10, pp. 5416-5427, DOI: 10.3390/e16105416, 2014.

[16] O. A. Herish, D. A. Ivan, R. H. Rashad, "Average Distance and Average Restricted Detour Distance of a Straight Chain of K-Wheels Graph," Palestine Journal of Mathematics, vol. 12 no. 4, pp. 399-409, 2023.

[17] M. A. Ahmed, J. A. Haveen, A. M. Gashaw, "Detour Polynomials of Generalized Vertex Identified of Graphs," Baghdad Science Journal, vol. 20 no. 2, pp. 705-712, DOI: 10.21123/bsj.2022.6350, 2023.

[18] H. Abdullah, I. Ali, "Restricted Detour Polynomial of a Straight Chain of Wheel Graphs," Al-Rafidain Journal of Computer Sciences and Mathematics (RJCM), vol. 17 no. 1, pp. 99-106, DOI: 10.33899/csmj.2023.179505, 2023.

[19] M. Azari, "On the Gutman Index of Thorn Graphs," Kragujevac Journal of Science, vol. no. 40, pp. 33-48, DOI: 10.5937/KgJSci1840033A, 2018.