Search

A connected even [2,2s]{[}2,2s]-factor of a graph G is a connected factor with all vertices of degree i(i=2,4,…,2s)i(i=2,4,\ldots ,2s), where s≥1s\ge 1 is an integer. In this paper, we show that a k+1s+2\tfrac{k+1}{s+2}-tough k-tree has a connected even [2,2s]{[}2,2s]-factor and thereby generalize the result that a k+13\tfrac{k+1}{3}-tough k-tree is Hamiltonian in [Hajo Broersma, Liming Xiong, and Kiyoshi Yoshimoto, Toughness and hamiltonicity in k-trees, Discrete Math. 307 (2007), 832–838].

The scattering number of a graph G is defined as s (G) = m a x { ω (G − X) − | X | : X ⊂ V (G) , ω (G − X) > 1 } , where X is a cut set of G, and ω (G − X) denotes the number of components in G − X , which can be used to measure the vulnerability of network G. In this paper, we generalize this parameter to a hypergraph to measure the vulnerability of uniform hypergraph networks. Firstly, some bounds on the scattering number are given. Secondly, the relations of scattering number between a complete k-uniform hypergraph and complete bipartite k-uniform hypergraph are discussed. [ABSTRACT FROM AUTHOR]

Vulnerability refers to the ability of a network to continue functioning when part of the network is either naturally damaged or targeted for attack. In this paper, the rupture degree of graphs is employed to measure the vulnerability of uniform linear hypergraphs. First, we discuss the bounds of the rupture degrees of k-uniform linear hypergraphs. Then, we give a recursive algorithm for computing the rupture degree of k-uniform hypertrees. [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 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]

For a given graph G = (V , E) , by τ (G) and ω (G) denote the order of the largest component and the number of connected components of G , respectively. The rupture degree of G is an important combinatorial parameters, which defined as r (G) = max { ω (G − X) − | X | − τ (G − X) : X ⊂ V (G) , ω (G − X) > 1 }. Clearly, the smaller the value r (G) is, the better the connectivity of graph G is. In this paper, the tree structures with minimum rupture degree be discussed, and the extremal graphs on the rupture degree in terms of graph girth are also characterized. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

For a given graph G = (V, E), its integrity is defined as I(G) = minX⊂V {|X|+m(G−X)}, where m(G−X) denote the order of the largest component of G−X. In [9], authors discuss the minimum integrity of tree with given order and the maximum degree. In this paper, we point that the result in [9] is flawed and by elementary method characterize the structure of the minimum integrity tree and thus correct Theorem 4.1 in [9]. Finally, we give the construction method of this kind of extremal graph. [ABSTRACT FROM AUTHOR]

For a given graph G = (V, E), its integrity is defined as I(G) = minX⊂V {|X|+m(G−X)}, where m(G−X) denote the order of the largest component of G−X. In [9], authors discuss the minimum integrity of tree with given order and the maximum degree. In this paper, we point that the result in [9] is flawed and by elementary method characterize the structure of the minimum integrity tree and thus correct Theorem 4.1 in [9]. Finally, we give the construction method of this kind of extremal graph. [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]

The edge rupture degree of a graph , as one of measurement parameter of network vulnerability, is defined as , where is the number of components of and is the order of a largest component of . In this paper, general results on the edge-rupture degree of a graph are considered. Firstly, some bounds on edge rupture degree are given. Further, edge rupture degree of some graphs is caculated. Also some results are given about this parameter with others. Finally, we discuss edge rupture degree of the complement graph and give the Nordhaus-Gaddum-type results for edge rupture degree. [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]

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]

For the complete graph Kn, its rupture degree is defined as 1-n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G - X)-|X|-m(G - X):X ⊂ V(G), ω(G - X) > 1 }, where ω(G - X) is the number of components of G - X and m(G - X) is the order of a largest component of G - X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree. [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]

We introduce a new graph parameter, the rupture degree. The rupture degree for a complete graph Kn is defined as 1 - n , and the rupture degree for an incomplete connected graph G is defined by r (G) =max {ω(G - X)- |X| - m(G - X) : X ⊂ V (G), ω(G - X) > 1}, where ω(G - X) is the number of components of G - X and m(G - X) is the order of a largest component of G - X. It is shown that this parameter can be used to measure the vulnerability of networks. Rupture degrees of several specific classes of graphs are determined. Formulas for the rupture degree of join graphs and some bounds of the rupture degree are given. We also obtain some Nordhaus–Gaddum type results for the rupture degree. [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]