The Open Monophonic Number of a Graph

For a connected graph G of order n, a subset S of vertices of G is a monophonic set of G if each vertex v in G lies on a x-y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A monophonic set of cardinality m(G) is called a m–set of G. A set S of vertices of a connected graph G is an open monophonic set of G if for each vertex v in G, either v is an extreme vertex of G and v ∈ S, or v is an internal vertex of a x-y monophonic path for some x, y ∈ S. An open monophonic set of minimum cardinality is a minimum open monophonic set and this cardinality is the open monophonic number, om(G). The open monophonic number of certain standard graphs are determined. For positive integers r, d and l ≥ 2 with r ≤ d ≤ 2r, there exists a connected graph of radius r, diameter d and open monophonic number l. It is proved that for a tree T of order n and diameter d, om(T) = n – d + 1 if and only if T is a caterpillar. Also for integers n, d and k with 2 ≤ d < n, 2 ≤ k < n and n – d – k + 1 ≥ 0, there exists a graph G of order n, diameter d and open monophonic number k. It is proved that om(G) – 2 ≤ om(G′) ≤ om(G) + 1, where G′ is the graph obtained from G by adding a pendant edge to G. Further, it is proved that if om(G′) = om(G) + 1, then v does not belong to any minimum open monophonic set of G, where G′ is a graph obtained from G by adding a pendant edge uv with v a vertex of G and u not a vertex of G. Keywords— Distance, geodesic, geodetic number, open geodetic number, monophonic number, open monophonic number. ——————————  ——————————