B-Edge Differential Measures for Structural Robustness of Certain Graph Classes

The use of graph-theoretic parameters is essential in interpreting the structural robustness, efficiency, and functionality of complex networks. Specifically, edge-based metrics are more useful in interpreting the susceptibility of links and the concept of upstream impact, as well as structural robustness. Such metrics are essential in a variety of fields such as network security, communication, and optimization theory. In the same way, a new edge-based invariant is introduced in this research paper, which is known as the b-edge differential. The b-edge differential is essentially linked to b-differential of a graph. Let G=V,E be a simple connected graph. For any subset of edges X⊆E, we associate the set BX=e∈E\X:e shares a common vertex with at least one edge in X}, that is, BX captures all edges outside X which are adjacent to X. The quantity ∂BEX=BX is called the b-edge differential of X. We then define the b-edge differential of a graph G by ∂BEG=maxX⊆E∂BEX. This parameter calculates the maximum value of the indirect dominances, or coverage, which can be achieved by a given set of edges. It serves as a useful tool in the identification of critical edges as well as the maximization of influence in networks. The problem can also be used in the applications involving the maximization of profit, traffic routing, and vulnerability evaluation for communication networks. We carry out the explicit computation of the b-edge differential for some classical types of graphs, such as paths, cyclic graphs, wheel graphs, complete graphs, star graphs, double-star graphs, comb graphs, complete bipartite graphs, ladder graphs, and triangular ladder graphs. The work described in this article expands the relevance of differential parameters in the theory of graphs, with promising research directions for theoretical and application aspects of network science.