Two kinds of conditional connectivity of hypercubes

Abstract

AbstractA subset [Formula: see text] is called an h-extra r-component cut of G if G – F is disconnected and there are at least r components, each component has at least h + 1 vertices. The cardinality of a minimum h-extra r-component cut of G, denoted by [Formula: see text] is the h-extra r-component connectivity of G. In this paper, we introduce a novel connectivity called the g-good r-component connectivity. For [Formula: see text] if G – F is disconnected and there are at least r components and each vertex [Formula: see text] has at least g neighbors, then F is called a g-good r-component cut of G; the g-good r-component connectivity of G, denoted by [Formula: see text] is the minimum cardinality of a g-good r-component cut of G. In this work, we prove that [Formula: see text] for [Formula: see text] and [Formula: see text] for [Formula: see text] where Qn is n-dimension hypercube.

Keywords

• h-extra r-component connectivity
• g-good r-component connectivity
• hypercube