The κ-edge Geodetic Number of a Graph
Abstract
For vertices u and v in a connected graph G = (V, E), the distance d(u, v) is the length of a shortest u - v path in G. A u - v path of length d(u, v) is called a u - v geodesic. A set S ⊆ V is a geodetic set of G if each vertex of G lies on a u-v geodesic for some vertices it and v in 5. The minimum cardinality of a geodetic set of G is the geodetic number g(G). A set S ⊆ V is an edge geodetic set of G if each edge of G lies lies on a u-v geodesic for some vertices u and v in S. The minimum cardinality of an edge geodetic set of G is the edge geodetic number eg(G). For an integer k ≥ 1, a geodesic of length k is called a k-geodesic. A set S ⊆ V is a k-geodetic set of G if each vertex v ε V - S lies on a k-geodesic of vertices in S. The minimum cardinality of a k-geodetic set of G is the k-geodetic number gk(G). A set S ⊆ V is a k-edge geodetic set of G if each edge e ε E - E(< S >) lies on a k-geodesic of vertices in S. The minimum cardinality of a kedge geodetic set of G is the k-edge geodetic number eg k(G). Graphs of order n having edge geodetic number n are characterized. Also, we characterize trees of diameter d for which the d-edge geodetic number and the edge geodetic number are equal. It is shown that for each triple a, 6, k of integers with 2 ≤ a ≤ 6 and k ≥ 2, there is a connected graph G with g k(G) = a and eg k(G) = 6. Also, it is shown that for integers a, b, c and k > 2 with 3 ≤ a ≤ b ≤ c, there exists a connected graph G such that g(G) = a, eg(G) = b and eg k(G) = c.
