A Study of Pancyclic Properties of Cartesian Product Graphs with Faulty Edges

  • 鄭 嘉文

Student thesis: Doctoral Thesis

Abstract

For interconnection network the existence of the cycle has many discussions and applications The pancyclic problem involves testing whether or not a graph contains cycles of all possible lengths Sometimes the length of the desired cycle satisfies some conditions For example the bipancyclic problem involves testing whether or not a graph contains cycles of all possible even lengths Edge-pancyclic property and edge-bipancyclic property are the extension of the above two properties A graph is edgepancyclic if each edge of graph lies on a cycle of every possible length And a graph is edge-bipancyclic if each edge of graph lies on a cycle of every possible even length When a network is activated the error may occur Many studies discuss whether or not a graph has some good fault-tolerant properties In other words they discuss whether or not the graph still satisfies some good properties (for example pancyclic property) when some vertices and edges are faulty A Cartesian product graph is generated by applying the graph Cartesian product operation “ × ” to factor networks Previous studies have investigated the various topological properties of Cartesian product graph In this dissertation we investigate the fault-free cycle embedding problems with edge faults on the Cartesian product graph Given two graphs which satisfy some specific properties the edge-fault pancyclic properties of Cartesian product of the two graphs are efficiently evaluated Those pancyclic properties are pancyclicity bipancyclicity edge-pancyclicity and edge-bipancyclicity We also show the obtained results are optimal for the number of faulty edges tolerated and those results are applied to two multiprocessor systems the nearest neighbor mesh hypercubes and generalized hypercubes both of which belong to Cartesian product graphs
Date of Award2015 Jun 24
Original languageEnglish
SupervisorSun-Yuan Hsieh (Supervisor)

Cite this

A Study of Pancyclic Properties of Cartesian Product Graphs with Faulty Edges
嘉文, 鄭. (Author). 2015 Jun 24

Student thesis: Doctoral Thesis