Jul 2026· Scientific Annals of Computer Science· Vol 36, pp. 107· 0 citations· 29 references
TL;DR
An explicit spectral construction is developed enabling the numerical validation algorithm to evaluate the time complexity in various structural configurations of (2n+1)-graphs, highlighting the substantial algorithmic demands for several graphs.
Abstract
This study investigates the path energy bounds of hub-centric graph families of order (2n+1), denoted by ℋ2n+1. The path energy is defined as the absolute sum of the eigenvalues of the path adjacency matrix Ap(ℋ2n+1), where each entry pij measures the maximum number of internally vertex- disjoint paths. Through an in-depth examination of the characteristic values of this matrix Ap(ℋ2n+1), we derive path energy bounds specific to these four (2n+1)-vertex graph, namely closed helm, double star, friendship, and double wheel graphs. We further developed an explicit spectral construction enabling the numerical validation algorithm to evaluate the time complexity in various structural configurations of (2n+1)-graphs. Also executed extensive trials to capture their average, maximum, and minimum computational performances. This analysis offers a detailed comparative study of the structural attributes that lead to computational complexity, highlighting the substantial algorithmic demands for several 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.
S. Sripriya, A. Anuradha· Baghdad Science Journal· 0 citations
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.
V. Kralev, Radoslava Kraleva, Aleksandra Popova· International Journal of Int...· 0 citations
The concept of graph energy, defined as the sum of the absolute eigenvalues of a graph's adjacency matrix, has been widely studied for its applications in chemistry and network theory. In this paper, we extend this notion to k-uniform hypergraphs by introducing the domination energy, a spectral invariant derived from a hypergraph's minimum dominating set. We introduce the domination matrix of a hypergraph, establish theoretical bounds for its energy, and explore its combinatorial properties. Furthermore, we demonstrate practical applications of this framework in supply chain risk management. By modeling multi-company production processes as hyperedges in a multi-layer hypergraph, we develop a mathematical framework for identifying critical companies whose disruption could paralyze entire supply chains. We develop algorithms with provable approximation guarantees, quantitative criticality metrics, and a tiered mitigation framework. This work bridges spectral hypergraph theory with real world complex system analysis, offering both theoretical contributions and practical tools for enhancing supply chain resilience. Since the domination matrix is a symmetric shift operator acting on signals supported on the hypergraph, the domination energy belongs to the family of spectral descriptors employed in graph and hypergraph signal processing and in multiscale network analysis. Consequently, the bounds established in this paper serve as structural information measures for higher-order networks and as groundwork for multiresolution methods on hypergraphs.
Abdulkafi Sanad, S. Mahde, Abdulqawe Kaed· International Journal of Wav...· 0 citations
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.
Saifur Rahman, Raju Doley· Acta Universitatis Sapientia...· 0 citations
Investigating the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover, presents randomized distributed algorithms that achieve nearly exponentially smaller energy complexity.
Mohsen Ghaffari, Zi Song Yeoh· ACM Symposium on Parallelism...· 1 citation
Gupta and Iosevich introduced the edge complexity of a graph as the minimum Fourier ratio of its adjacency matrix over all vertex labelings and bounded it below by graph energy divided by the square root of twice the number of edges. We characterize equality for a fixed labeling: the Fourier transform of the adjacency matrix must have at most one nonzero entry in each row and column. This implies regularity, circulancy of every positive even power of an extremizing adjacency matrix, and a parity restriction on connected components, and it gives equality results for certain Laplacian spectral projectors. We construct equality cases from affine involutions on cyclic groups. Singer difference sets yield, for every prime power $q$, an equality-attaining $(q+1)$-regular graph that is not an abelian Cayley graph. We also establish Fourier-ratio estimates for weak, Cartesian, and strong graph products, including preservation of equality under weak products of coprime orders. We use Fourier-ratio recovery as a coding theorem to obtain entropy upper bounds for low-complexity adjacency matrices and complement them with a lower bound obtained by perturbing complete graphs. Finally, a concentration argument shows that if $Np_N/\log N\to\infty$ and $\limsup_{N\to\infty}p_N<1$, then $\operatorname{FR}_{\min}(G(N,p_N))$ is of order $N$ with probability tending to one.
Vishal Gupta, A. Iosevich, J. Iosevich et al.· 0 citations