Evaluating the Influence of Graph Density on the Efficiency of Shortest Path Algorithms Using Different Data Structures

Partition-based construction and stability analysis of Euler graphs using vertex strength

The ‘divide and conquer’ paradigm proves to be one of the most frequently used techniques for dealing with the complexities of graph-related problems. Therefore, it is of great importance to measure the tendency of a vertex to be critical and its susceptibility in a graph. The criticality of a vertex is often analysed in terms of its strength. Removing a highly critical vertex from a graph modelling a network may introduce vulnerability into the system represented by the graph. Minimizing the vulnerability of such a network without affecting its fundamental structure, thereby improving the stability of the graph, is the primary objective of the article. To achieve this, certain properties of Euler graphs are analysed in terms of vertex strength, and a method is presented for determining all possible constructions of Euler graphs corresponding to different integer partitions. The parts of a partition represent the vertex strengths, and their sum corresponds to the total vertex strength of the graph. Various connectivity indices are employed to validate the proposed constructions. Furthermore, their interrelationships and potential real-life applications are also discussed. It is evident from the constructions that they may play a vital role in developing network deception technology to protect digital assets, as each partition of the network generates a distinct network.

Finding Simple Shortest-Paths via Centroids

A Spectral Approach to Join Based Operations on Graphs

This study explores the spectral characteristics and energy distributions associated with selected graph operations derived from the first Zagreb, second Zagreb, and sum-connectivity matrices to contribute to understanding how algebraic operations induce spectral energy shifts analogous to perturbations in physical or molecular graph systems.

Effect of Vertex and Edge Deletion on Total Irregularity Index

Cut vertices and bridges are significant graph parts that help to separate large graphs into smaller ones to ease the calculations that need to be made by means of smaller and easier steps. Recently, the effect of removing such graph parts on several topological graph indices has been calculated. Removal of a vertex means that a member is discarded from a network together with the member's connections, and removal of an edge corresponds to removing the connection between two members in the network. Thus, the reliability of a network can be increased by removing some unwanted vertices and edges from the network by using the formulas provided here for several vertex and edge types. This paper considers the effect of vertex and edge removal on the total irregularity index. It removes several different vertex and edge types from a network and calculates their effects on the total irregularity index. The method employed here can be applied to other irregularity indices and even to other graph-theoretical indices to measure the effect of vertex or edge removal on such indices.

The Importance of Dijkstra Graph Algorithm in Route Opimization

Route optimization is a critical component in transportation, logistics, and network systems, where efficiency directly impacts cost, time, and resource utilization. Among shortest path algorithms, Dijkstra’s algorithm remains a cornerstone due to its ability to compute optimal routes in weighted graphs with non-negative edge costs. This study evaluates the importance of Dijkstra’s algorithm in route optimization by combining theoretical analysis with empirical experimentation. A well-defined experimental framework was established using standardized datasets, including DIMACS road network benchmarks and OpenStreetMap (OSM) regional extracts, to ensure reproducibility and comparability. Graph types were clearly specified: sparse graphs representing rural networks, dense graphs modeling urban transportation systems, and multi-criteria weighted graphs incorporating distance, travel time, and congestion factors. Experiments were conducted in a controlled computational environment comprising an Intel Xeon CPU, 32GB RAM, and Python NetworkX implementation, with performance metrics including execution time, memory usage, scalability, and path accuracy. Comparative analysis against A* search Algorithm, ALT (A* search Landmarks and Triangle inequality), and Arc Flags algorithms demonstrated that Dijkstra consistently achieved faster computation times (up to 40% improvement), lower memory overhead, and higher accuracy in path selection, resulting in significant reductions in delivery and planning time. The findings confirm Dijkstra’s enduring relevance in modern applications such as GPS navigation, logistics management, and network routing. Furthermore, the study highlights opportunities for integrating Dijkstra’s algorithm with real-time traffic data and intelligent systems to enhance adaptive route optimization in dynamic environments

A Novel Edge-Efficiency-Based Algorithm for Hamiltonian Cycle and Path Detection in Graphs

Searching for the existence of a Hamiltonian cycle and path connecting all nodes in a graph is an NP-complete problem. This article proposes the E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights. The Kmax and Kmin that are particular spanning trees are generated first to obtain the fundamental cuts. Then, each edge's total number in the fundamental cuts is obtained to state edge efficiency. Next, all nodes are navigated with a method that determines priority, starting with the highest degree node at the most efficient edge. Thus, when the greedy traversal succeeds, a Hamiltonian cycle or path is constructed between all nodes. Since E² is a deterministic greedy algorithm without backtracking, it does not guarantee finding a Hamiltonian cycle in every Hamiltonian graph; however, it always terminates in polynomial time. These methods are used for the first time to obtain the Hamiltonian cycle in this study. In addition, we present an object-oriented construction to avoid getting exponential algorithm complexity. Finally, to prove the correctness of the method, we show whether some general graphs are Hamiltonian using the proposed method.