Paired many-to-many disjoint path covers in faulty hypercubes

DOI10.1016/j.tcs.2013.10.008zbMath1352.68195MaRDI QIDQ391966

Shinhaeng Jo, Jung-Heum Park, Kyung-Yong Chwa

Publication date: 13 January 2014

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

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

zbMATH Keywords

hypercube; graph theory; fault tolerance; disjoint path cover; strongly Hamiltonian laceability

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

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

68M15: Reliability, testing and fault tolerance of networks and computer systems

05C45: Eulerian and Hamiltonian graphs

Related Items

Unpaired Many-to-Many Disjoint Path Covers on Bipartite k-Ary n-Cube Networks with Faulty Elements, Hamiltonicity of hypercubes with faulty vertices, A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs, Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest, Algorithms for finding disjoint path covers in unit interval graphs, Paired many-to-many disjoint path covers in restricted hypercube-like graphs, Fault-tolerant cycles embedding in hypercubes with faulty edges, Generalized Gray codes with prescribed ends, Many-to-many disjoint paths in hypercubes with faulty vertices, Paired many-to-many disjoint path covers of hypertori, A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph, Paired 2-disjoint path covers of multidimensional torus networks with faulty edges, Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes, Ore-type degree conditions for disjoint path covers in simple graphs, Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs, One-to-one disjoint path covers in digraphs, The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks, Torus-like graphs and their paired many-to-many disjoint path covers, Hamiltonian paths in hypercubes with local traps, Vertex-disjoint paths joining adjacent vertices in faulty hypercubes, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Disjoint path covers with path length constraints in restricted hypercube-like graphs, Disjoint path covers joining prescribed source and sink sets in interval graphs, Many-to-many two-disjoint path covers in restricted hypercube-like graphs, Disjoint path covers in cubes of connected graphs

Cites Work

• Unnamed Item
• Fault-tolerant cycle embedding in the hypercube
• Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
• Embedding a ring in a hypercube with both faulty links and faulty nodes
• Longest paths and cycles in faulty star graphs
• Long paths and cycles in hypercubes with faulty vertices
• Many-to-many disjoint paths in faulty hypercubes
• Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults
• Paired many-to-many disjoint path covers of hypercubes with faulty edges
• Longest fault-free paths in hypercubes with vertex faults
• Fault-tolerant cycles embedded in hypercubes with mixed link and node failures
• Path partitions of hypercubes
• Linear array and ring embeddings in conditional faulty hypercubes
• Fault-tolerant Hamiltonian laceability of hypercubes.
• Spanning multi-paths in hypercubes
• Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
• Hamiltonian properties on the class of hypercube-like networks
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• Hamiltonian-laceability of star graphs
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• Hamiltonian Cycles with Prescribed Edges in Hypercubes