Analyzing Detour Distance and Domination Number in Special Graph Classes

Abstract

In this paper, we investigate the relationship between detour distance and domination number within various special classes of graphs. The detour distance between two vertices is defined as the length of the longest path connecting them, and it provides an alternative metric to the traditional geodesic distance in graph theory. By integrating this concept with domination theory, we introduce new structural measures that capture the extended influence of vertices beyond their immediate neighborhoods. We define and analyze the detour domination number, denoted as γDD(G), which represents the minimum cardinality of a set of vertices such that every vertex in the graph lies on a detour path from at least one dominating vertex. We examine the behavior of this parameter in specific graph classes, including complete graphs, paths, cycles, trees, and grid graphs, deriving exact values or bounds where applicable. Additionally, we study the upper detour domination number, investigate its extremal properties, and explore how it contrasts with traditional domination metrics. We also characterize graph classes where the detour domination number equals the classical domination number and where it significantly diverges. The results contribute to a deeper understanding of detour-based influence in graphs, offering new perspectives for applications in network resilience, transport systems, and distributed computing, where long-range reachability and control are essential.