An Application of Bellman-Ford Algorithm in Hyperbolic Graph

Gromov Hyperbolicity of Substitution graphs

In this paper, we construct a class of infinite graphs, called substitution graphs. The vertex set consists of all finite words over a finite alphabet. A directed graph is formed by adding vertical edges connecting each word to its children and horizontal edges defined recursively by two finite directed graphs G and J: edges among vertices with the same parent follow G, while edges between vertices whose parents are horizontally linked follow J. The substitution graph is defined as its underlying graph. Substitution graphs provide a purely combinatorial model of self-similar structures, independent of any underlying geometric structure. Furthermore, we establish a necessary and sufficient condition for substitution graphs to be hyperbolic, formulated in terms of the vanishing of path matrices associated with sufficiently long shortest horizontal paths. Based on this characterization, we further derive several conditions that are either necessary or sufficient for hyperbolicity, depending only on the generators G and J.

Pseudo A4-graphs and their properties in dihedral groups

Let G be a finite group. We introduce a new graph definition, called the pseudo A4-graph, as an extension of the classical A4-graph. The pseudo A4-graph of G or PA4-graph is a simple graph ΓG whose vertices are elements of G, and two distinct vertices a and b are joined by an edge if and only if ab−1 = ba−1. This paper presents the formulas for certain graph invariants such as the number of edges, diameter, total degree, chromatic number, clique number, independence number, domination number, matching number, and graph energy. The method involves constructing the A4-graphs of dihedral groups, analyzing their structure, and systematically computing graph invariants through algebraic reasoning and combinatorial techniques to establish fundamental properties and relationships. One of the results in this paper comply with the well-known fact that the energy of a graph is always an even integer.

A novel approach for constructing a minimum spanning tree

The spanning tree of a graph is obtained when all vertices of a graph are connected in such a way that no cycle is formed. This work proposes a new algorithm that, at each round, selects a maximal independent set of vertices (an inclusion-maximal, not necessarily maximum-cardinality, set of pairwise non-adjacent vertices) and attaches to every vertex of that set its cheapest cycle-safe incident edge to find a minimum spanning tree of any weighted graph. The procedure organizes safe-edge selections into batches indexed by maximal independent sets; its number of such batching rounds depends on the maximal independent sets selected, and this notion of a round is not directly comparable to a single iteration of Prim's or Kruskal's algorithm without further definition. Using the classical cut property, we prove that the procedure always produces a minimum spanning tree of a connected graph. If r denotes the number of independent-set rounds, a straightforward sequential implementation has worst-case running time O(r(n+m)+m log m). We do not claim, and this paper does not prove, that the number of rounds is minimized over all possible choices of maximal independent sets, nor that the resulting sequential running time improves on the classical O(m log n) bounds. This work may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.

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

This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.

ARITHMETICAL STRUCTURES ON

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs

We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.