## Abstract

A bipartite graph G = (V, E) is said to be bipancyclic if it contains a cycle of every even length from 4 to | V |. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_{v} (respectively, F_{e}) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_{n}. In this paper, we show that every edge of Q_{n} - F_{v} - F_{e} lies on a cycle of every even length from 4 to 2^{n} - 2 | F_{v} | even if | F_{v} | + | F_{e} | ≤ n - 2, where n ≥ 3. Since Q_{n} is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.

Original language | English |
---|---|

Pages (from-to) | 1802-1808 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 156 |

Issue number | 10 |

DOIs | |

Publication status | Published - 2008 May 28 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics