Edge-bipancyclicity of star graphs with faulty elements

Chao Wen Huang, Hui Ling Huang, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph Sn. Given a set F comprised of faulty vertices and/or edges in Sn with |F|≤n-3 and any fault-free edge e in Sn-F, we show that there exist cycles of every even length from 6 to n!-2|Fv| in Sn-F containing e, where n<3. Our result is optimal because the star graph is both bipartite and regular with the common degree n-1. The length of the longest fault-free cycle in the bipartite Sn is n!-2|Fv| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!-2|Fv|+2 to n!-2|F v| can be embedded.

Original languageEnglish
Pages (from-to)6938-6947
Number of pages10
JournalTheoretical Computer Science
Volume412
Issue number50
DOIs
Publication statusPublished - 2011 Nov 25

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Edge-bipancyclicity of star graphs with faulty elements'. Together they form a unique fingerprint.

Cite this