**Abstract:** |
The connectivity of a network – the minimum number of nodes whose removal will disconnect the network – is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness and measurement for the fault-tolerance of the network. To provide more accurate measures for the fault-tolerance of networks than the connectivity, some generalizations of connectivity have been introduced. We extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let $H$ be a certain particular connected subgraph of
$G$. The H-structure connectivity of graph $G$, denoted $\kappa(G; H)$, is the cardinality of a minimal set of subgraphs $F$ = { $H_{1}$, $H_{2}$, …, $Hm$} in $G$, such that every $H_{i} \in F$ is isomorphic to $H$, and $F$'s removal will disconnect $G$. The $H$-substructure connectivity of graph $G$, denoted $\kappa^{s}(G; H)$, is the cardinality of a minimal set of subgraphs $F$ = { $J_{1}$, $J_{2}$, …, $Jm$}, such that every $J_{i} \in F$ is a connected subgraph of $H$, and $F$'s removal will disconnect $G$. |
---|