Conditional matching preclusion for the arrangement graphs

DOI10.1016/j.tcs.2011.07.007zbMath1234.68322OpenAlexW2047201685MaRDI QIDQ653318

Eddie Cheng, Marc J. Lipman, László Lipták, David J. Sherman

Publication date: 9 January 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.007

zbMATH Keywords

interconnection networksmatching preclusion number of a graph

Mathematics Subject Classification ID

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

A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs ⋮ Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs ⋮ Strong matching preclusion for augmented cubes ⋮ Matching preclusion for balanced hypercubes ⋮ Conditional matching preclusion number of graphs ⋮ The symmetry property of (n,k)‐arrangement graph ⋮ Path and cycle fault tolerance of bubble-sort graph networks ⋮ Strong matching preclusion number of graphs ⋮ Matching preclusion and conditional matching preclusion for regular interconnection networks ⋮ Fractional matching preclusion of product networks ⋮ On the eigenvalues of certain Cayley graphs and arrangement graphs ⋮ Fault tolerance in the arrangement graphs ⋮ The (conditional) matching preclusion for burnt pancake graphs ⋮ Cayley graph on symmetric group generated by elements fixing \(k\) points ⋮ Fractional matching preclusion for arrangement graphs ⋮ Link Failure Tolerance in the Arrangement Graphs ⋮ Matching preclusion for cube-connected cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved deterministic algorithms for weighted matching and packing problems
• Embedding longest fault-free paths onto star graphs with more vertex faults
• The super connectivity of the pancake graphs and the super laceability of the star graphs
• Matching preclusion for \(k\)-ary \(n\)-cubes
• Strong matching preclusion
• A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem
• Weak-vertex-pancyclicity of (\(n,k\))-star graphs
• Conditional matching preclusion sets
• Conditional matching preclusion for hypercube-like interconnection networks
• On the surface area of the \((n,k)\)-star graph
• Arrangement graphs: A class of generalized star graphs
• Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
• On the arrangement graph.
• Embedding longest fault-free paths in arrangement graphs with faulty vertices
• Conditional matching preclusion for the alternating group graphs and split-stars
• On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs
• MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS
• A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs
• A new class of interconnection networks based on the alternating group
• Matching preclusion for some interconnection networks
• Embedding of cycles in arrangement graphs
• Longest fault-free paths in star graphs with vertex faults