Upper edge-to-vertex detour monophonic number of a graph

Abstract

For a connected graph G = (V,E) of order at least three, the monophonic distance dm(u, v) is the length of a longest u−v monophonic path in G. A u − v path of length dm(u, v) is called a u − v detour monophonic. For subsets A and B of V , the monophonic distance dm(A,B) is defined as dm(A,B) = min｛dm(x, y) : x ∈ A, y ∈ B｝. A u−v path of length dm(A, B) is called an A−B detour monophonic path joining the sets A,B ⊆ V, where u ∈ A and v ∈ B. A set S ⊆ E is called an edge-to-vertex detour monophonic set of G if every vertex of G is incident with an edge of S or lies on a detour monophonic path joining a pair of edges of S. The edge-to-vertex detour monophonic number dmev(G) of G is the minimum cardinality of its edge-to-vertex detour monophonic sets and any edge-to-vertex detour monophonic set of car- dinality dmev(G) is an edge-to-vertex detour monophonic basis of G. An edge-to-vertex detour monophonic set S in a connected graph G is called a minimal edge-to-vertex detour monophonic set of G if no proper subset of S is an edge-to-vertex detour monophonic set of G. The upper edge-to-vertex detour monophonic number dm+ ev(G) of G is the maxi- mum cardinality of a minimal edge-to-vertex detour monophonic set of G. We determine bounds for it and certain general properties of these concepts are studied. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dmev(G) = a and dm+ ev(G) = b.