World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Strong Fault-Hamiltonicity for the Crossed Cube and Its Extensions

    Fault-Hamiltonicity is an important measure of robustness for interconnection networks. Given a graph G=(V,E). The goal is to ensure that GF remains Hamiltonian for every FVE such that |F|k for some k. Obviously, one wants the best k possible. For many interconnection networks, in particular, for the crossed cube, the optimal result is known. There is a natural bound for k as the resulting graph cannot have a vertex of degree at most 1. Thus, if r is the minimum degree in G, then kr2. Since interconnection networks are modeled after computer networks, it is reasonable to assume that the vertex/edge faults occur following certain probability distributions. As such, it is reasonable to assume that it is unlikely for a vertex to have degree at most 1 even if r − 1 vertices/edges are deleted. Thus we may be able to delete more vertices and/or vertices if we assume that all the faults are “not clustered” at a vertex. To be precise, the goal is to find the best possible k in which GF remains Hamiltonian for every FVE such that |F|k and the minimum degree of G − F is at least 2. In this paper, we study this problem for the crossed cube and then extend the result to cover a large subclass of bijective connection networks as well as the more general matching composition networks.

    Communicated by K. Qiu