On k-Geodetic Edge Traceable Graph

Abstract

A graph G is k-geodetic edge traceable if every edge of G lies in at least one geodesic of length k. The maximum geodesic edge-covering number $$\textrm{gec}_{\max }(G)$$ is the minimum number of largest fixed-length geodesics that cover all edges of G. We study some properties of k-geodetic edge traceable graphs and establish relations between $$\textrm{gec}_{\max }(G)$$ and the domination number of a connected graph. We investigate the k-geodetic edge traceability of the complete bipartite graph $$K_{m,n}$$ , and provide an algorithm to compute $$\textrm{gec}_{\max }(K_{n,m})$$ . We also study the k-geodetic edge traceability of trees and product graphs, namely the Cartesian, strong, lexicographic, and Corona products, and obtain bounds for $$\textrm{gec}_{\max }$$ of these product graphs.