The (conditional) matching preclusion for burnt pancake graphs

DOI10.1016/j.dam.2013.01.010zbMath1287.05117OpenAlexW2050169367MaRDI QIDQ2446329

Huiqing Liu, Xiaolan Hu

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.01.010

zbMATH Keywords

interconnection networksperfect matchingburnt pancake graph(conditional) matching preclusion set/number

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (18)

Vulnerability analysis of multiprocessor system based on burnt pancake networks ⋮ Matching preclusion for vertex-transitive networks ⋮ Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs ⋮ Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs ⋮ Strong matching preclusion for augmented cubes ⋮ Paired 2-disjoint path covers of burnt pancake graphs with faulty elements ⋮ Strong matching preclusion of \((n,k)\)-star graphs ⋮ Conditional fractional matching preclusion for burnt pancake graphs and pancake-like graphs (extended abstract) ⋮ Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults ⋮ Matching preclusion for \(n\)-grid graphs ⋮ Matching preclusion for \(k\)-ary \(n\)-cubes with odd \(k \geq 3\) ⋮ Conditional matching preclusion for regular bipartite graphs and their Cartesian product ⋮ Matching preclusion for direct product of regular graphs ⋮ Fractional matching preclusion number of graphs and the perfect matching polytope ⋮ Neighbor connectivity of pancake graphs and burnt pancake graphs ⋮ Fault tolerance and diagnosability of burnt pancake networks under the comparison model ⋮ Matching preclusion for cube-connected cycles ⋮ Matching preclusion for \(n\)-dimensional torus networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching preclusion and conditional matching preclusion for regular interconnection networks
• Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
• Matching preclusion for \(k\)-ary \(n\)-cubes
• Conditional matching preclusion for the arrangement graphs
• Fault-tolerant routing in burnt pancake graphs
• Conditional matching preclusion sets
• Conditional matching preclusion for hypercube-like interconnection networks
• Bounds for sorting by prefix reversal
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• On the problem of sorting burnt pancakes
• Fault tolerant routing in the star and pancake interconnection networks
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars
• A group-theoretic model for symmetric interconnection networks
• Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry
• Matching preclusion for some interconnection networks

This page was built for publication: The (conditional) matching preclusion for burnt pancake graphs