The upper edge-to-vertex detour number of a graph

Abstract

For two vertices u and v in a graph G = (V, E), the detour distance D(u, v) is the length of a longest u-v path in G. A u-v path of length D(u, v) is called a u-v detour. For subsets A and B of V, the detour distance D(A, B) is defined as D(A, B) = min{D(x, y): x ∈ A, y ∈ B}. A u-v path of length D(A, B) is called an A-B detour joining the sets A, B ⊆ V where u ∈ A and v ∈ B. A vertex x is said to lie on an A-B detour if x is a vertex of an A-B detour. A set S ⊆ E is called an edge-to-vertex detour set if every vertex of G is incident with an edge of S or lies on a detour joining a pair of edges of S. The edge-to-vertex detour number dn₂(G) of G is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order dn₂(G) is an edge-to-vertex detour basis of G. An edge-to-vertex detour set S in a connected graph G is called a minimal edge-to-vertex detour set of G if no proper subset of S is an edge-to-vertex detour set of G. The upper edge-to-vertex detour number, dn₂⁺(G) of G is the maximum cardinality of a minimal edge-to-vertex detour set of G. The upper edge-to-vertex detour numbers of certain standard graphs are obtained. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dn2(G) = a and dn₂⁺(G) = b.