| Summary: | It is known widely that an interconnection network can be denoted by a graph <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mo>=</mo> <mo>(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula>, where <i>V</i> denotes the vertex set and <i>E</i> denotes the edge set. Investigating structures of <i>G</i> is necessary to design a suitable topological structure of interconnection network. One of the critical issues in evaluating an interconnection network is graph embedding, which concerns whether a host graph contains a guest graph as its subgraph. Linear arrays (i.e., paths) and rings (i.e., cycles) are two ordinary guest graphs (or basic networks) for parallel and distributed computation. In the process of large-scale interconnection network operation, it is inevitable that various errors may occur at nodes and edges. It is significant to find an embedding of a guest graph into a host graph where all faulty nodes and edges have been removed. This is named as fault-tolerant embedding. The twisted hypercube-like networks (<inline-formula> <math display="inline"> <semantics> <mrow> <mi>T</mi> <mi>H</mi> <mi>L</mi> <mi>N</mi> <mi>s</mi> </mrow> </semantics> </math> </inline-formula>) contain several important hypercube variants. This paper is concerned with the fault-tolerant path-embedding of <i>n</i>-dimensional (<i>n</i>-<i>D</i>) <inline-formula> <math display="inline"> <semantics> <mrow> <mi>T</mi> <mi>H</mi> <mi>L</mi> <mi>N</mi> <mi>s</mi> </mrow> </semantics> </math> </inline-formula>. Let <inline-formula> <math display="inline"> <semantics> <msub> <mi>G</mi> <mi>n</mi> </msub> </semantics> </math> </inline-formula> be an <i>n</i>-<i>D</i><inline-formula> <math display="inline"> <semantics> <mrow> <mi>T</mi> <mi>H</mi> <mi>L</mi> <mi>N</mi> </mrow> </semantics> </math> </inline-formula> and <i>F</i> be a subset of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>V</mi> <mrow> <mo>(</mo> <msub> <mi>G</mi> <mi>n</mi> </msub> <mo>)</mo> </mrow> <mo>∪</mo> <mi>E</mi> <mrow> <mo>(</mo> <msub> <mi>G</mi> <mi>n</mi> </msub> <mo>)</mo> </mrow> </mrow> </semantics> </math> </inline-formula> with <inline-formula> <math display="inline"> <semantics> <mrow> <mo>|</mo> <mi>F</mi> <mo>|</mo> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </semantics> </math> </inline-formula>. We show that for two different arbitrary correct vertices <i>u</i> and <i>v</i>, there is a faultless path <inline-formula> <math display="inline"> <semantics> <msub> <mi>P</mi> <mrow> <mi>u</mi> <mi>v</mi> </mrow> </msub> </semantics> </math> </inline-formula> of every length <i>l</i> with <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo>-</mo> <mn>1</mn> <mo>≤</mo> <mi>l</mi> <mo>≤</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>-</mo> <msub> <mi>f</mi> <mi>v</mi> </msub> <mo>-</mo> <mn>1</mn> <mo>-</mo> <mi>α</mi> </mrow> </semantics> </math> </inline-formula>, where <inline-formula> <math display="inline"> <semantics> <mrow> <mi>α</mi> <mo>=</mo> <mn>0</mn> </mrow> </semantics> </math> </inline-formula> if vertices <i>u</i> and <i>v</i> form a normal vertex-pair and <inline-formula> <math display="inline"> <semantics> <mrow> <mi>α</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> if vertices <i>u</i> and <i>v</i> form a weak vertex-pair in <inline-formula> <math display="inline"> <semantics> <mrow> <msub> <mi>G</mi> <mi>n</mi> </msub> <mo>-</mo> <mi>F</mi> </mrow> </semantics> </math> </inline-formula> (<inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </semantics> </math> </inline-formula>).
|
|---|