Jun 2026· Journal of new theory· pp. 1-13· 0 citations· 9 references
TL;DR
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.
Abstract
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.
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 adjacenc...
V. Kralev, Radoslava Kraleva, Aleksandra Popova· International Journal of Int...· 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...
Saifur Rahman, Raju Doley· Acta Universitatis Sapientia...· 0 citations
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 e...
Kexiang Xu, Ivan Damnjanović, Urovs Milivojevi'c et al.· arXiv.org· 0 citations
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 paper investigates the parameterized complexity of this problem and obtains an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot k})$ algorithms.
Alexander Firbas, R. Ganian, Sylvain Meunier et al.· arXiv.org· 0 citations
Here, the most natural parameters such as the budgets d and a of the players, the vertex cover number and treewidth of the input graph, and combinations of these parameters are considered, showing that the encoding of the costs and weights of the edges has a considerable influence on the problem complexity.
Christian Komusiewicz, Zhenwei Liu, Nils Morawietz et al.· International Workshop on Gr...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
