On the Edge Monophonic Number of a Graph

J. John, P. Arul Paul Sudhahar

For a connected graph $G=(V,E)$, an edge monophonic set of $G$ is a set $M\subseteq V(G)$ such that every edge of $G$ is contained in a monophonic path joining some pair of vertices in $M$. The edge monophonic number $m_1(G)$ of $G$ is the minimum order of its edge monophonic sets and any edge monophonic set of order $m_1(G)$ is a minimum edge monophonic set of $G$. Connected graphs of order $p$ with edge monophonic number $p$ are characterized. Necessary condition for edge monophonic number to be $p-1$ is given. It is shown that for every two integers $a$ and $b$ such that $2\leq a \leq b$, there exists a connected graph $G$ with $m(G)=a$ and $m_1(G)=b$, where $m(G)$ is the monophonic number of $G$.