TOWARD GENERAL CLASSIFICATIONS OF K-GEODETIC GRAPHS: STRUCTURAL FOUNDATIONS, ALGORITHMIC CHALLENGES, AND EMERGING RESEARCH DIRECTIONS

Abstract

The general classifications of k-geodetic graphs, for each of their families , remain notoriously difficult open problems in discrete mathematics. A k-geodetic graph G is a connected one in which every pair of vertices is joined by at most k shortest paths, where G is geodetic if , bigeodetic if , and trigeodetic if , making these structures fundamental to graph theory, combinatorial optimization, and network design. Despite decades of research primarily dealing with geodetic graphs, and more recently, dealing with bigeodetic and trigeodetic ones, no comprehensive structural characterizations have been established. This paper reviews the principal mathematical barriers that have prevented complete classifications and discusses recent structural approaches based on embedded even graphs, bigeodetic graphs, and combinatorial design theory. Particular attention is given to the algorithmic challenges associated with generating and enumerating k-geodetic graphs, where exhaustive computational methods become NP-hard. The paper further explores the use of Balanced Incomplete Block Designs (BIBDs) as algebraic seeds for constructing higher-order k-geodetic structures while substantially reducing computational search complexity. Finally, several future research directions are proposed, including connections between k-geodetic graph theory and number theory, and applications in communication network topology, quantum routing architectures, graph neural networks, computational complexity, and exploratory mathematical models connecting discrete graph spaces with continuous physical systems.