Linearly many faults in Cayley graphs generated by transposition trees

DOI10.1016/j.ins.2007.05.034zbMath1129.68050OpenAlexW1975574007MaRDI QIDQ2456457

László Lipták, Eddie Cheng

Publication date: 18 October 2007

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2007.05.034

zbMATH Keywords

Cayley graphsstar graphbubble-sort graphInterconnection networkstransposition treesuperconnectedness

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items (50)

Inferring contagion patterns in social contact networks with limited infection data ⋮ Finding outbreak trees in networks with limited information ⋮ The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM\(^\ast\) model ⋮ Component connectivity of the hypercubes ⋮ Parallel routing in regular networks with faults ⋮ On the conditional diagnosability of matching composition networks ⋮ Edge-fault-tolerant strong Menger edge connectivity of bubble-sort graphs ⋮ LINEARLY MANY FAULTS IN (n, k)-STAR GRAPHS ⋮ Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars ⋮ The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs ⋮ Cyclic vertex-connectivity of Cayley graphs generated by transposition trees ⋮ On extra connectivity and extra edge-connectivity of balanced hypercubes ⋮ A new approach to finding the extra connectivity of graphs ⋮ Linearly many faults in arrangement graphs ⋮ Conditional edge-fault-tolerant Hamiltonicity of the data center network ⋮ A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks ⋮ Conditional connectivity of Cayley graphs generated by transposition trees ⋮ Two-disjoint-cycle-cover bipancyclicity of bubble-sort star graphs ⋮ The (E)FTSM-(edge) Connectivity of Cayley Graphs Generated by Transposition Trees ⋮ The Component Diagnosability of General Networks ⋮ The spanning cyclability of Cayley graphs generated by transposition trees ⋮ A kind of conditional connectivity of transposition networks generated by \(k\)-trees ⋮ A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees ⋮ The conditional fault diagnosability of \((n, k)\)-star graphs ⋮ Extra (component) connectivity and diagnosability of bubble sort networks ⋮ Linearly many faults in Cayley graphs generated by transposition triangle free unicyclic graphs ⋮ Diagnosability of star graphs with missing edges ⋮ The 3-good-neighbor connectivity of modified bubble-sort graphs ⋮ Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees ⋮ Conditional diagnosability of alternating group networks ⋮ Fault-tolerant maximal local-connectivity on bubble-sort star graphs ⋮ A kind of conditional connectivity of Cayley graphs generated by wheel graphs ⋮ A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs ⋮ Fault diagnosability of arrangement graphs ⋮ Conditional fault diagnosis of hierarchical hypercubes ⋮ Orienting Cayley graphs generated by transposition trees ⋮ Neighbor connectivity of two kinds of Cayley graphs ⋮ Bipancyclic properties of Cayley graphs generated by transpositions ⋮ Reliability assessment of the Cayley graph generated by trees ⋮ The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model ⋮ Super \(R^k\)-vertex-connectedness ⋮ Conditional connectivity of star graph networks under embedding restriction ⋮ A note on generalized matching preclusion in bipartite graphs ⋮ Linearly many faults in 2-tree-generated networks ⋮ On reliability of the folded hypercubes in terms of the extra edge-connectivity ⋮ Component Edge Connectivity of Hypercubes ⋮ Edge fault tolerance of graphs with respect to \(\lambda_{2}\)-optimal property ⋮ CONDITIONAL FAULT DIAGNOSABILITY OF DUAL-CUBES ⋮ Fault tolerance and diagnosability of burnt pancake networks under the comparison model ⋮ Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs
• On the Day-Tripathi orientation of the star graphs: connectivity
• Hyper Hamiltonian laceability on edge fault star graph
• Arrangement graphs: A class of generalized star graphs
• The 4-star graph is not a subgraph of any hypercube
• The \((n,k)\)-star graph: A generalized star graph
• Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars.
• Super-connectivity and super-edge-connectivity for some interconnection networks
• Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
• Restricted connectivity for three families of interconnection networks
• FAULT RESILIENCY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITIONS
• Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs
• Maximal vertex-connectivity of
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• A group-theoretic model for symmetric interconnection networks
• Congestion-free, dilation-2 embedding of complete binary trees into star graphs
• On the genus of star graphs
• Fault Hamiltonicity and fault Hamiltonian connectivity of the (n,k)-star graphs
• Increasing the connectivity of the star graphs
• Cluster fault-tolerant routing in star graphs
• A new class of interconnection networks based on the alternating group
• Routing properties of supercubes

This page was built for publication: Linearly many faults in Cayley graphs generated by transposition trees