Search

Let G = ( V , E ) be a connected graph and P be graph-theoretic property. A network is often modeled by a graph G = ( V , E ) . One fundamental consideration in the design of networks is reliability. The connectivity is an important parameter to measure the fault tolerance and reliability of network. The conditional connectivity λ(G, P) or κ(G, P) is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects G and each remaining component has property P. Let F be a vertex set or edge set of G and P be the property of with at least k components. Then we have the k-component connectivity cκk(G) and the k-component edge connectivity cλk(G). In this paper, we determine the k-component (edge) connectivity of locally twisted cubes LTQn for small k, and we also prove other properties of LTQn.

Let G be a connected graph with vertex set V, minimum degree and edge-connectivity . If is a real number, then the zeroth-order general Randi index is defined by xVdeg(x), where deg(x) denotes the degree of the vertex x. A graph is maximally edge-connected if =. In this paper, we present sufficient conditions for connected graphs (resp. connected triangle-free graphs) to be maximally edge-connected in terms of the zeroth-order general Randi index, the order and the minimum degree when (,0) or (1,2] (resp. [1,0)(1,2]).

For a connected graph with order n and size m, the cyclomatic number (=number of independent cycles) is equal to γ = m - n + 1 . The graphs with γ = 1 are referred to the unicyclic graphs. In this paper, we characterized completely the unicyclic graphs with n vertices having maximum degree resistance distance.

Fault tolerance is especially important for interconnection networks, since the growing size of networks increases their vulnerability to component failures. A classical measure for the fault tolerance of a network in the case of vertex failures is its connectivity. The connectivity κ (G) of a connected graph G is the least positive integer κ such that there is S ⊂ V, |S| = κ and G–S is disconnected or reduces to the trivial graph K1. The edge connectivity λ(G) of G is similarly defined. It is well known that κ (G) ≤ λ (G) ≤ δ (G). A graph G is called maximally (edge) connected if κ (G) = δ (G)( λ (G) = δ (G)), max-κ (max-λ) for simply. A connected graph G = (V, E) is called supper- κ (resp. super-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. We introduce a new kind of network called k-split network. A network based on a graph G = (X1 U X2 U … ⊂ Xk, I, E) is called a k-split network, if its vertex set V can be partitioned into κ + 1 stable sets I, X1, X2, …, Xκ such that X1 U X2 U … U Xκ induces a complete k-partite graph and an independent set I. In this note, we show that: G = (X1UX2 … UXκ, I, E) is a non-complete connected κ-split graph with κ ≥ 3 and |X1| ≤ |X2| ≤ … ≤ |Xκ|. Then we have (1) If |X1 U X2 … U Xκ–1| ≥ δ(G), then κ (G) = δ (G). (2) If |X1 U X2 … U Xκ–1|δ, then G is super-κ. (5) G is super-λ.

Let G be a connected graph with order n=|V(G)|, minimum degree @[email protected](G) and edge-connectivity @[email protected](G). A graph is said to be maximally edge-connected if @[email protected] In this paper, we present two sufficient conditions for (triangle-free) graphs to be maximally edge-connected in terms of its order and the Zeroth-order general Randic index.

Let $$G$$G be a connected graph with order $$n,$$n, minimum degree $$\delta =\delta (G)$$?=?(G) and edge-connectivity $$\lambda =\lambda (G).$$?=?(G). A graph $$G$$G is maximally edge-connected if $$\lambda =\delta .$$?=?. In this paper, we present two sufficient conditions for graphs to be maximally edge-connected, which generalize two results recently proved by P. Dankelmann, A. Hellwig and L. Volkmann. The extremal graphs are also characterized.