Effect of Vertex and Edge Deletion on Total Irregularity Index

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.

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.

Edge transmission irregular graphs

The transmission of a vertex $v$ in a connected graph $G$ is the sum of distances from $v$ to all vertices in $G$. A transmission irregular (TI) graph is a connected graph in which any two distinct vertices have different transmissions. We extend the concept of transmission to edges by defining the transmission of an edge as the sum of the transmissions of its two endpoints. A connected graph can now be called edge transmission irregular (ETI) if any two distinct edges have different transmissions. We show that almost all graphs are not ETI and then investigate several related order realizability problems involving chemical ETI graphs. In particular, we prove that for every $n \ge 15$, there exists a subcubic tree of order $n$ that is both TI and ETI.

Edge-defect matrices and stability of the Kirchhoff index for complete graphs with deleted edges

In this paper, we study the effective resistance, the Kirchhoff index, and the number of spanning trees of the connected graph $K_n-F$, which is obtained from the complete graph by deleting a set $F$ of $p$ edges. Let $B$ be the incidence matrix of the deleted edges. We call the matrix $Q=B^TB$ the edge-defect matrix. This is a $p\times p$ matrix which records, with signs, the way in which the deleted edges share their end vertices. First, we derive a formula for the effective resistance between any two distinct vertices in terms of the resolvent of the edge-defect matrix. This reduces the usual computation using the $n\times n$ Laplacian matrix to a computation using a $p\times p$ matrix corresponding to the number of deleted edges. Moreover, by using the eigenvalues of the same matrix, we give unified formulas for the Kirchhoff index and the number of spanning trees. Next, we derive a stability identity which exactly describes the excess from the Xu, Das, and Zhang type lower bound. As a consequence, we show that, in the range where a matching deletion can be realized, the Kirchhoff index is minimized when the deleted edge set is a matching. Furthermore, by using majorization, we prove that, for $p\ge 2$ and $n\ge \max\{4,2p-1\}$, among all non-matching deleted edge sets, the minimum is attained only when the deletion graph is isomorphic to $P_3\cup(p-2)K_2$. Finally, we apply the obtained formulas to several deletion graphs, such as matchings, stars, cliques, paths, and cycles.

Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms

Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal is to find vertex permutations on one or both layers that minimize the induced number of edge crossings. This problem is NP-hard, and crossing-minimal solutions may still contain many crossings. Recently, there has been growing interest in an orthogonal optimization goal, namely removing all crossings by vertex splitting, i.e., replacing original vertices by two or more copies and distributing the adjacencies among them. In this paper, we study a natural extension of the two-layer vertex splitting problem in which the vertex order on one layer is constrained by a given auxiliary tree $T$, motivated by applications such as the visualization of anatomical hierarchies in the Human Reference Atlas. We investigate the parameterized complexity of this problem and obtain two main contributions: (1) a fixed-parameter algorithm with respect to the number $k$ of splits, and (2) an ETH-tight single-exponential fixed-parameter algorithm with respect to the maximum degree of $T$. Moreover, we build on the latter result to obtain an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot \log k})$ algorithms. Finally, we also implement our algorithm and show that it performs well in practice.

Preventing Small Global Cuts by Protecting Edges