Search

The generalized k -connectivity κ k (G) of a graph G , introduced by Hager in 1985, is a natural generalization of the concept of connectivity κ (G) , which is just for k = 2. Rongxia Hao et al. determined the generalized 4-connectivity of the total graphs of the complete equipartition bipartite graph and conjectured that κ 4 (T (K m , m + 1)) = 2 m − 1 and κ 4 (T (K m , n)) = 2 m for n > m + 1 and m ≥ 4 in [Appl. Math. Comput. 422 (2022)]. In this paper, we solved this conjecture. [ABSTRACT FROM AUTHOR]

Abstract The generalized k -connectivity κ k (G) of a graph G , introduced by Hager (1985), is a natural generalization of the concept of connectivity κ (G), which is just for k = 2. This parameter is often used to measure the capability of a network G to connect any k vertices in G. The line graph and the total graph are usually seen as important models for interconnection networks. In this paper, we determine the generalized 3-(edge-)connectivity of the line graph and the total graphs of the complete bipartite graph and discuss the bound for generalized 3-connectivity of the total graphs. [ABSTRACT FROM AUTHOR]

For a given graph G = ( V , E ) , denote by m ( G ) and ω ( G ) the order of the largest component and the number of components of G , respectively. The scattering number of G is defined as s ( G ) = max { ω ( G − X ) − | X | : X ⊆ V , ω ( G − X ) > 1 } , and the rupture degree r ( G ) = max { ω ( G − X ) − | X | − m ( G − X ) : X ⊆ V ( G ) , ω ( G − X ) > 1 } . These two parameters are related to reliability and vulnerability of networks. In this paper, we present some new bounds on the scattering number and rupture degree of a graph G in terms of its connectivity κ ( G ) and genus γ ( G ). Furthermore, we give graphs to show these bounds are best possible. [ABSTRACT FROM AUTHOR]

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G . Simoes Pereira gave the formula of cycle multiplicity for line and total graph of forests. Recently, Akbar Ali determined cycle multiplicity of total graph for C n and K 1, n . In this paper, we determine the cycle multiplicity of some Cartesian product graphs, the total graphs of complete graph, complete bipartite graph and unicycle graph, which generalize the results of Akbar Ali and Panayappan (2010) in [1]. [ABSTRACT FROM AUTHOR]

Graph burning is a deterministic discrete time graph process that can be interpreted as a model for the spread of influence in social networks. The burning number b (G) of a graph G is the minimum number of steps in a graph burning process for that graph. In this paper, we introduced a new graph parameter, the generalized burning number of a graph b r (G) , which is generalization of b (G) with b 1 (G) = b (G). And then determined the generalized burning number of several graphs and operation graphs. The general bounds on this parameter are also discussed. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. The weak rupture degree of G is defined as r w (G) = max { ω (G − X) − | X | − m e (G − X) : ω (G − X) > 1 } , where the maximum is taken over all X , the subset of V (G), ω (G − X) is the number of components in G − X , and m e (G − X) is the size (edge number) of a largest component in G − X. This is an important parameter to quantitatively describe the invulnerability of networks. In this paper, based on a study of relationship between network structure and the weak rupture degree, a polynomial algorithm for computing the weak rupture degree of trees is given. [ABSTRACT FROM AUTHOR]