Hamiltonian Paths in Restricted Hypercube-Like Graphs with Edge Faults


The KIPS Transactions:PartA, Vol. 18, No. 6, pp. 225-232, Dec. 2011
10.3745/KIPSTA.2011.18.6.225,   PDF Download:

Abstract

Restricted Hypercube-Like (RHL) graphs are a graph class that widely includes useful interconnection networks such as crossed cube, Mobius cube, Mcube, twisted cube, locally twisted cube, multiply twisted cube, and generalized twisted cube. In this paper, we show that for an m-dimensional RHL graph G, m≥4, with an arbitrary faulty edge set F⊂E(G), |F|≤m-2, graph G＼F has a hamiltonian path between any distinct two nodes s and t if dist(s, V(F))≠1 or dist(t, V(F))≠1. Graph G＼F is the graph G whose faulty edges are removed. Set V(F) is the end vertex set of the edges in F and dist(v, V(F)) is the minimum distance between vertex v and the vertices in V(F).


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. Y. Kim and B. T. Chun, "Hamiltonian Paths in Restricted Hypercube-Like Graphs with Edge Faults," The KIPS Transactions:PartA, vol. 18, no. 6, pp. 225-232, 2011. DOI: 10.3745/KIPSTA.2011.18.6.225.

[ACM Style]
Sook Yeon Kim and Byung Tae Chun. 2011. Hamiltonian Paths in Restricted Hypercube-Like Graphs with Edge Faults. The KIPS Transactions:PartA, 18, 6, (2011), 225-232. DOI: 10.3745/KIPSTA.2011.18.6.225.