Graph mutation, graph distance, and graph gradient

Most networks constantly change, and predicting links or recovering from link failures is crucial for maintaining a network. Distance-based graph invariants are important criteria for network maintenance. A graph mutation is a change in the edge set of a graph, and a graph gradient is the change in a graph invariant after a mutation. We present the general concepts of discrete integral and derivative for vertex and edge weighted graphs as a tool. Using the concepts, some related problems are solved more efficiently, flexibly, and simpler than the existing solutions.Let G=(V(G), E(G)) be a graph with vertex weight function f_G and edge weight function w_G. And d_G (u,v) denotes the distance of u,v∈V(G), the minimum sum of edge weights across all the paths connecting u and v. Then assumeW_(α,β) (G)=∑_({u,v}⊆V(G))[αf_G⁡(u) ×f_G(v)+β(f_G⁡(u) +f_G⁡(v)) ] d_G (u,v) , α,β∈R, and T is a spanning tree (ST) of G. If an edge e∈E(T) fails, it creates T-e with two components. If T-e reconnected with ε∈E(G)\E(T) and form T_(ε\e)=T+ε-e such that W_(α,β) (T_(ε\e)) is minimum, then ε is a best swap edge (BSE) of e w.r.t W_( α,β). We devise an algorithm that finds a BSE ε∈E(G)\E(T) w.r.t W_( α,β) for each e∈E(T) and computes W_( α,β) (T_(ε\e) ). We call the algorithm "all best swap edges w.r.t. W_( α,β)"(ABSEW). Preprocessing for ABSEW takes O(n)-time, whereas solving ABSEW has an average time-complexity of O((m-n)log n) and a best time-complexity of O(m-n), all in O(m)-space, where (m,n)=(|E(G)|,|V(G)|). For dense graphs, however, the average time reaches O(m-n). T's routing cost (RC) for a given set of sources S⊆ V(G) equals ∑_((a,b)∈V(T)×S )d_T (u,v). For 2-edge-connected positively edge-weighted graphs and some specified |S|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of O(m2^O(α(2m,2m)) .log^2 n) (|S|=O(1) or n), O(m.log n+n^2 ) (|S|=2), and O(mn) (|S|>2) for the specified |S|'s. Our algorithm outperforms existing algorithms regarding RC with no limit on |S|, edge and vertex weights, or graph type, while also computing the RC for each BSE. Assume T is a positively weighted n-vertex tree, and e∈ E(T) fails. If we reconnect the components of T-e with ε∈E(T^c) such that, W_( α,β) (T_(ε\e) ) is minimum, then ε is called a best switch (BS) of e w.r.t. W_(α,β). For the inputs e∈ E(T) and w,α,β ∈R^+, we find ε, T_(ε\e), and W_(α,β) (T_(ε\e) ) with the worst average time of O(log⁡〖n)〗 and the best average time of O(1) where ε is a BS of e w.r.t. W_(α,β) and the weight of ε is w. There are comparable algorithms to ours only w.r.t W_( 1,0) or W_( 0,1) which are relatively complicated and limited. In our algorithm α,β can be changed at any step without affecting complexities or preprocessing.A subgraph H of a simple graph G is isomeric if d_G (u,v)=d_H (u,v), ∀u,v∈V(H). And G is distance-preserving if it has at least a k-vertex isometric subgraph for each k, 1≤k≤|V(G)|. There is a relatively old conjecture by Nussbaum and Esfahanian that says: if deg_G (v)>n/2, ∀v∈V(G), then G is distance-preserving. We will have a close asymptotic approach to the conjecture.One added edge to a simple graph G (w_G=1) is called inset edge and mutates G. Establishing some regular and extensive matrix tools, we devised an algorithm that computes and sorts the gradient of the inset edges of a tree regarding the total distance, D(G)=∑_({u,v}⊆V(G))d_G (u,v) for G. The algorithms' average time complexity is minimal, reducing the previous algorithm from O(n^5) to an average of n^2 O(log⁡n), where n=|V(G)|. Indeed, we compute the total distance of O(n^2) unicyclic graphs each on average of O(log⁡n)-time and the best time of O(1).