Extreme Monophonic Graphs and Extreme Geodesic Graphs

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 monophonic set of $G$ is a set $S$ of vertices such that every vertex of $G$ lies on a monophonic path joining some pair of vertices in $S$. The monophonic number of $G$ is the minimum cardinality of its monophonic sets and is denoted by $m(G)$. A geodetic set of $G$ is a set $S$ of vertices such that every vertex of $G$ lies on a geodesic joining some pair of vertices in $S$. The geodetic number of $G$ is the minimum cardinality of its geodetic sets and is denoted by $g(G)$. The number of extreme vertices in $G$ is its extreme order $ex(G)$. A graph $G$ is an extreme monophonic graph if $m(G)=ex(G)$ and an extreme geodesic graph if $g(G)=ex(G)$. Extreme monophonic graphs of order $p$ with monophonic number $p$ and $p-1$ are characterized. It is shown that every pair $a,b$ of integers with $0 \leq a \leq b$ is realized as the extreme order and monophonic number, respectively, of some graph. For positive integers $r,d$ and $k \geq 3$ with $r < d$, it is shown that there exists an extreme monophonic graph $G$ of monophonic radius $r$, monophonic diameter $d$, and monophonic number $k$. Also, we give a characterization result for a graph $G$ which is both extreme geodesic and extreme monophonic.