Open AccessMaximally and super connected multisplit graphs and digraphs
Author(s) -
Lingjun Guo,
Guifu Su,
Lutz Volkmann,
Xingke Zhao
Publication year - 2019
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm170716024g
Subject(s) - combinatorics , mathematics , vertex connectivity , vertex (graph theory) , connectivity , graph , discrete mathematics
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 connectivities. A network based on a graph G = (X1?X2?...? Xk,I,E) is called a k-multisplit network, if its vertex set V can be partitioned into k+1 stable sets I,X1,X2,...,Xk such that X1 ?X2?...?Xk induces a complete k-partite graph and I is an independent set. In this note, we first show that: for any non-complete connected k-multisplit graph G = (X1?X2?...?Xk,I,E) with k ? 3 and |X1| ? |X2| ?...? |Xk|, each of the following holds (1) If |X1?X2?...?Xk-1| ? ?, then k(G) = ?(G). (2) If |X1?X2?...?Xk-1| < ?, then k(G)? |X1? X2?...? Xk-1|. (3) ?(G) = ?(G). (4) If |X1?X2?...?Xk-1| > ? with respect to |X1| ? 2 and ? ? 2, then G is super-k. (5) G is super-?. In addition, we present sufficient conditions for digraphs to be maximally edge-connected and super-edge connected in terms of the zeroth-order general Randic index of digraphs.