Embedded connectivity of recursive networks

DOI10.1016/J.TCS.2016.09.022MaRDI QIDQ329723zbMATH OpenOpenAlexFDO

Authors Xiang-Jun Li, Qi-Qi Dong, Zheng Yan, Jun-Ming Xu

Publication date 21 October 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.04113

zbMATH Keywords

fault-toleranceconnectivityhypercubesstar graphs\(h\)-super connectivitybubble-sort graphsembedded connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10)

Abstract: Let $G_n$ be an $n$-dimensional recursive network. The $h$-embedded connectivity $zet{a}_h(G_n)$ (resp. edge-connectivity $et{a}_h(G_n)$) of $G_n$ is the minimum number of vertices (resp. edges) whose removal results in disconnected and each vertex is contained in an $h$-dimensional subnetwork $G_h$. This paper determines $zet{a}_h$ and $et{a}_h$ for the hypercube $Q_n$ and the star graph $S_n$, and $et{a}_3$ for the bubble-sort network $B_n$.

Recommendations

• Embedded connectivity of \( (n, k)\)-star graphs
• Embedded connectivity of ternary \(n\)-cubes
• Conditional connectivity of recursive interconnection networks respect to embedding restriction
• Embedded connectivity of complete-transposition graphs
• Conditional connectivity of star graph networks under embedding restriction

Cites work

• scientific article; zbMATH DE number 2010366 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Conditional connectivity
• Conditional connectivity of Cayley graphs generated by transposition trees
• Conditional connectivity of recursive interconnection networks respect to embedding restriction
• Conditional connectivity of star graph networks under embedding restriction
• Fault tolerance measures for m-ary n-dimensional hypercubes based on forbidden faulty sets
• Generalized measures for fault tolerance of star networks
• On conditional edge-connectivity of graphs

Cited in

(12)

• Conditional connectivity of recursive interconnection networks respect to embedding restriction
• Matroidal connectivity and conditional matroidal connectivity of star graphs
• Embedded connectivity of ternary \(n\)-cubes
• On recurrent and recursive interconnection patterns
• Embedded Edge-Connectivity Reliability Evaluation of Augmented Hypercube Interconnection Networks
• Embedded connectivity of complete-transposition graphs
• Generalized measures of fault tolerance for bubble sort networks
• Embedded edge connectivity of \(k\)-ary \(n\)-cubes
• Embedded connectivity of \( (n, k)\)-star graphs
• Note on reliability of star graphs
• Reliability of \(m\)-ary \(n\)-dimensional hypercubes under embedded restriction
• scientific article; zbMATH DE number 4057550 (Why is no real title available?)

This page was built for publication: Embedded connectivity of recursive networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329723)