Connectivity for some families of composition networks

Hong Chen, Meirun Chen, Michel Habib, Cheng Kuan Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Connectivity of a connected graph G, κ(G), is an important index in exploring network topology which is the minimal number of vertices that need to be removed to separate G into disconnected or trivial. Let G0,G1,…,Gm−1 be m connected graphs of the same order. A matching composition network G is constructed by adding an arbitrary perfect matching between G0 and G1. For m≥3, a cycle composition network H is constructed by adding an arbitrary perfect matching between Gi and Gi+1(modm) for each 0≤i≤m−1. This construction has been so widely used in literature to build networks in which fault diagnosability can be studied, that it is worth to study their connectivity in detail, this is the main purpose of this paper. In this paper, we determine (1) κ(G)=δ(G) if κ(G0)+κ(G1)≥δ(G); otherwise, κ(G)≥κ(G0)+κ(G1), and (2) κ(H)=δ(H) if ∑i=0m−1κ(Gi)≥δ(H); otherwise, κ(H)≥∑i=0m−1κ(Gi). Examples show those bounds are tight. We then generalize these examples to a general composition using matchings on which we propose a conjecture on the connectivity and prove it for an important particular case.

Original languageEnglish
Pages (from-to)361-367
Number of pages7
JournalTheoretical Computer Science
StatePublished - 24 Jun 2022


  • Connectivity
  • Cycle composition networks
  • Matching composition networks


Dive into the research topics of 'Connectivity for some families of composition networks'. Together they form a unique fingerprint.

Cite this