Embedding fault-free hamiltonian paths with prescribed linear forests into faulty ternary n-cubes

Abstract The k-ary n-cube is an important underlying topology for large-scale multiprocessor systems. A linear forest in a graph is a subgraph each component of which is a path. In this paper, we investigate the problem of embedding hamiltonian paths passing through a prescribed linear forest in ternary n-cubes with faulty edges. Given a faulty edge set F with at most 2 n − 3 edges and a linear forest L with at most 2 n − 3 − | F | edges, for two distinct vertices in the ternary n-cube, we show that the ternary n-cube admits a fault-free hamiltonian path between u and v passing through L if and only if none of the paths in L has u or v as internal vertices or both of them as end-vertices.

• Publication year

  2019

• Venue

  Theoretical Computer Science

• Publication date

  2019-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/J.TCS.2018.09.020
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Embedding various cycles with prescribed paths into k-ary n-cubes

  2017cited by this paper
• Fault-Free Hamiltonian Cycles Passing through Prescribed Edges in k-Ary n-Cubes with Faulty Edges

  2015cited by this paper
• Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges

  2014cited by this paper
• Fault-free Hamiltonian cycles passing through a linear forest in ternary nn-cubes with faulty edges

  2013cited by this paper
• Pancyclicity of k-ary n-cube networks with faulty vertices and edges

  2012cited by this paper
• k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model

  2012cited by this paper
• Hamiltonian Cycles through Prescribed Edges in k-Ary n-Cubes

  2011cited by this paper
• Hamiltonian cycles passing through linear forests in k-ary n-cubes

  2011cited by this paper
• Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

  2011cited by this paper
• Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

  2011cited by this paper
• Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

  2010cited by this paper
• Path embeddings in faulty 3-ary n-cubes

  2010cited by this paper
• Bipanconnectivity and Bipancyclicity in k-ary n-cubes

  2009cited by this paper
• Hamiltonian paths and cycles passing through a prescribed path in hypercubes

  2009cited by this paper
• Panconnectivity and edge‐pancyclicity of k‐ary n‐cubes

  2009cited by this paper
• Why should we integrate services, servers, and networking in a data center?

  2009cited by this paper
• Fault-free cycles passing through prescribed paths in hypercubes with faulty edges

  2009cited by this paper
• A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

  2008cited by this paper
• Embedding Long Paths in k-Ary n-Cubes with Faulty Nodes and Links

  2008cited by this paper
• Graph Theory

  2008cited by this paper
• Hamiltonian paths with prescribed edges in hypercubes

  2007cited by this paper
• Cycles passing through prescribed edges in a hypercube with some faulty edges

  2007cited by this paper
• Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

  2007cited by this paper
• Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

  2006cited by this paper
• Hamiltonian Cycles with Prescribed Edges in Hypercubes

  2005cited by this paper
• Blue Gene/L torus interconnection network

  2005cited by this paper
• Pancyclicity on Möbius cubes with maximal edge faults

  2004cited by this paper
• Longest Fault-Free Paths in Star Graphs with Edge Faults

  2001cited by this paper
• The k-ary n-cube network : modeling, topological properties and routing strategies

  1999cited by this paper
• Performance of the CRAY T3E Multiprocessor

  1997cited by this paper
• Lee Distance and Topological Properties of k-ary n-cubes

  1995cited by this paper
• Cray T3D: a new dimension for Cray Research

  1993cited by this paper
• All-To-All Broadcast and Applications On the Connection Machine

  1992cited by this paper
• Performance of the Intel iPSC/860 and Ncube 6400 hypercubes

  1991cited by this paper
• iWarp: a 100-MOPS, LIW microprocessor for multicomputers

  1991cited by this paper
• Performance Analysis of k-Ary n-Cube Interconnection Networks

  1987cited by this paper
• Citation for Published Item: Use Policy Bipancyclicity in K-ary N-cubes with Faulty Edges under a Conditional Fault Assumption

  year unknowncited by this paper

• Embedding Hamiltonian Paths with Prescribed Linear Forests into k-ary n-Cube Networks

  2024cites this paper
• Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges

  2023cites this paper
• Fault-tolerant Hamiltonian connectivity of 2-tree-generated networks

  2022cites this paper
• Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links

  2022cites this paper
• Hamiltonian paths of k-ary n-cubes avoiding faulty links and passing through prescribed linear forests

  2021cites this paper
• Prescribed Hamiltonian Connectedness of 2D Torus

  2020cites this paper
• Matchings extend to Hamiltonian cycles in hypercubes with faulty edges

  2019cites this paper
• Fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes

  2019cites this paper
• Optimality for the restricted edge connectivity in exchanged ternary n-cubes

  year unknowncites this paper