EXTREME MONOPHONIC GRAPHS AND EXTREME GEODESIC GRAPHS

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 amonophonic path if it is a chordless path. Amonophonic set of G is a set S of vertices such that every vertex of G lies on amonophonic 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). Extrememonophonic graphs of order p withmonophonic number p and p - 1 are characterized. It is shown that every pair a, b of integers with 0 <= a <= b is realized as the extreme order and monophonic number, respectively, of some graph. For positive integers r, d and k >= 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.