The Detour Monophonic Number of a Graph

Abstract

For a connected graph $G=(V,E)$ of order at least two, a chord of a path $P$ is an edge joining two non-adjacent vertices of $P$. A path $P$ is called a monophonic path if it is a chordless path. A longest $x-y$ monophonic path is called an $x-y$ detour monophonic path. A set $S$ of vertices of $G$ is a monophonic set of $G$ if each vertex $v$ of $G$ lies on an $x-y$ monophonic path for some elements $x$ and $y$ in $S$. The minimum cardinality of a monophonic set of $G$ is the monophonic number of $G$, denoted by $m(G)$. A set $S$ of vertices of $G$ is a detour monophonic set of $G$ if each vertex $v$ of $G$ lies on an $x-y$ detour monophonic path for some $x$ and $y$ in $S$. The minimum cardinality of a detour monophonic set of $G$ is the detour monophonic number of $G$ and is denoted by $dm(G)$. We determine bounds for it and characterize graphs which realize these bounds. Also, for each pair $a,b$ of integers with $2\le a\le b$, we prove that there is a connected graph $G$ with $m(G)=a$ and $dm(G)=b$.