TY - JOUR AU - Titus, P. AU - Santhakumaran, A.P PY - 2016/12/30 Y2 - 2024/03/29 TI - Extreme Monophonic Graphs and Extreme Geodesic Graphs JF - Tamkang Journal of Mathematics JA - Tamkang J. Math. VL - 47 IS - 4 SE - Papers DO - 10.5556/j.tkjm.47.2016.2045 UR - https://journals.math.tku.edu.tw/index.php/TKJM/article/view/2045 SP - 393-404 AB - 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. ER -