Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Chia Wen Cheng, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

Abstract

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to 2⌊n(G)2⌋, where n(G) is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to n(G), where r≥3. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where n(G), n(H)≥ 9, let k1, k2≥5 be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph G×H with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of NQmr,⋯,m1 and GQmr,⋯,m1.

Original languageEnglish
Pages (from-to)767-781
Number of pages15
JournalJournal of Computer and System Sciences
Volume82
Issue number5
DOIs
Publication statusPublished - 2016 Aug 1

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges'. Together they form a unique fingerprint.

Cite this