On the higher-order edge-tenacity of a graph

Abstract

The area of graph vulnerability concerns the question of how much communication in a network is disrupted by the deletion of edges from the graph. The most fundamental measure of graph vulnerability of a connected graph is the edge-connectivity of the graph. One of the motivations in studying the edge-tenacity of a graph is that it can be a more refined measure of vulnerability than that based on simple edge-connectivity. The first-order edge-tenacity Ti (G) of a graph G is defined as (Equation presented) The quantity ω(G - X) - 1 can be interpreted as the number of additional components that are created by removing the set X of edges from the connected graph G. Then the set X that minimizes (Equation presented) is the set whose removal minimizes the number of edges deleted and the size of the largest component, per additional component created. The smaller the edgetenacity, the more vulnerable is the graph. The edge-tenacity becomes a more significant measurement in comparing the vulnerability of two graphs when they have the same edge-connectivity. For an integer k, 1 ≥ k ≥|V(G)| - 1, we define the k-order edgetenacity of a graph G as (Equation presented)Where the minimum is taken over all edge cutsets X of G. We define G - X to be the graph induced by the edges of E(G) - X, τ(G - X) is the number of edges in the largest component of the graph induced by G - X and ω(G - X) is the number of components of G - X. The objective of this paper is to study first this generalized concept of edge-tenacity. Besides giving the bounds and relationships of the A:-order edge tenacity of a graph G. We also prove that for any positive integers r, s satisfying r/s < s ≤ r, there exists an infinite family of graphs such that for each graph G in the family, Λ(G) = r (where A(G) is the edge-connectivity of G), T₁ (G) = s, and G can be factored into s spanning trees. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.