Search

For a given graph G = (V , E) , denote by m (G) and ω (G) the order of the largest component and the number of connected components of G , respectively. The scattering number of G is defined as s (G) = max { ω (G − X) − | X | : X ⊆ V , ω (G − X) ≠ 1 }. The tenacity of G is defined as T (G) = min { | X | + m (G − X) ω (G − X) : X ⊆ V , ω (G − X) ≠ 1 }. These two theoretical parameters are important combinatorial parameters for measuring the vulnerability of networks. In this paper, we determine the scattering number and tenacity of k -uniform linear hypergraph G k . [ABSTRACT FROM AUTHOR]

Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph. [ABSTRACT FROM AUTHOR]

By rewriting the problem of computing the scattering number of a split graph as minimization of a submodular function on a crossing family, we show that this problem can be solved in polynomial time. At the same time, three other vulnerability parameters, namely, the integrity, tenacity and rupture degree of split graphs are determined. [ABSTRACT FROM AUTHOR]