The Monophonic Detour Hull Number of a Graph

Abstract

For vertices $u$ and $v$ in a connected graph $G=(V,E)$, the monophonic detour distance $d_m(u,v)$ is the length of a longest $u-v$ monophonic path in $G$. An $u-v$ monophonic path of length $d(u,v)$ is an $u-v$ monophonic detour or an $u-v$ $m$-detour. The set $I_{d_m}[u,v]$ consists of all those vertices lying on an $u-v$ $m$-detour in $G$. Given a set $S$ of vertices of $G$, the union of all sets $I_{d_m}[u,v]$ for $u,v\in S$, is denoted by $I_{d_m}[S]$. A set $S$ is an $m$-detour convex set if $I_{d_m}[S]=S$. The $m$-detour convex hull $[S{]}_{d_m}$ of $S$ in $G$ is the smallest $m$-detour convex set containing $S$.

A set $S$ of vertices of $G$ is an $m$-detour set if $I_{d_m}[S]=V$ and the minimum cardinality of an $m$-detour set is the $m$-detour number $md(G)$ of $G$. A set $S$ of vertices of $G$ is an $m$-detour hull set if $[S{]}_{d_m}=V$ and the minimum cardinality of an $m$-detour hull set is the $m$-detour hull number $m{d}_h(G)$ of $G$.

Certain general properties of these concepts are studied. Bounds for the $m$-detour hull number of a graph are obtained. It is proved that every two integers $a$ and $b$ with $2\le a\le b$ are realizable as the $m$-detour hull number and the $m$-detour number respectively, of some graph. Graphs $G$ of order $n$ for which $m{d}_h(G)=n$ or $m{d}_h(G)=n-1$ are characterized. It is proved that for each triple $a$, $b$, and $k$ of positive integers with $a<b$ and $k\ge 3$, there exists a connected graph $G$ with $ra{d}_m(G)=a$, $dia{m}_m(G)=b$, and $m{d}_h(G)=k$.