Matching preclusion number in product graphs

DOI10.1016/j.tcs.2018.06.050zbMath1416.05242MaRDI QIDQ1725689

Christopher Melekian, Eddie Cheng, Zhao Wang, Yaping Mao

Publication date: 14 February 2019

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

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

zbMATH Keywords

cluster; corona; join; interconnection networks; Cartesian product; perfect matching; strong product; direct product; lexicographic product; matching preclusion

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C76: Graph operations (line graphs, products, etc.)

Related Items

Construction of k-matchings in graph products, Conditional matching preclusion number of graphs, Fractional matching preclusion numbers of Cartesian product graphs, Conditional matching preclusion for regular bipartite graphs and their Cartesian product, A note on maximum fractional matchings of graphs, Fractional matching preclusion number of graphs, The fractional matching preclusion number of complete \(n\)-balanced \(k\)-partite graphs, Fractional matching preclusion of product networks, The fractional (strong) matching preclusion number of complete \(k\)-partite graph, Fractional matching preclusion number of graphs and the perfect matching polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching preclusion for vertex-transitive networks
• \(\{2,3\}\)-extraconnectivities of hypercube-like 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 hypercube-like interconnection networks
• Comparative study of product networks
• Matching preclusion for balanced hypercubes
• Fault-tolerant path embedding in folded hypercubes with both node and edge faults
• Matching preclusion and conditional matching preclusion problems for the folded Petersen cube
• Matching preclusion for \(n\)-dimensional torus networks
• Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
• Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs
• 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
• MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS
• Fault Hamiltonicity and fault Hamiltonian connectivity of the (n,k)-star graphs
• Robust recoverable perfect matchings
• Matching preclusion for some interconnection networks