Cycle embedding in alternating group graphs with faulty elements

Ping Ying Tsai, Yu Tzu Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Cycle embedding is an important issue in evaluating the efficiency of interconnection networks. In this paper, we show that an n-dimensional alternating group graph AGn has the following results, where F is the set of faulty vertices and/or faulty edges in AGn : (1) For n ≥ 4, AGn-F is edge 4-pancyclic if |F| ≤ n − 4; and (2) For n ≥ 3, AGn-F is vertex-pancyclic if |F| ≤ n − 3. All the results are optimal with respect to the number of faulty elements tolerated, and they are improvements over the cycle embedding properties of alternating group graphs proposed previously in several articles.

Original languageEnglish
Title of host publicationAdvanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013
PublisherSpringer Verlag
Number of pages1
ISBN (Print)9789400772618
DOIs
Publication statusPublished - 2014 Jan 1
Externally publishedYes
EventAdvanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013 - , Taiwan
Duration: 2013 Aug 232013 Aug 25

Publication series

NameLecture Notes in Electrical Engineering
Volume260
ISSN (Print)1876-1100
ISSN (Electronic)1876-1119

Conference

ConferenceAdvanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013
CountryTaiwan
Period13/8/2313/8/25

    Fingerprint

Keywords

  • Alternating group graph
  • Cayley graph
  • Cycle embedding
  • Fault-tolerant
  • Interconnection network
  • Pancyclicity

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this

Tsai, P. Y., & Lin, Y. T. (2014). Cycle embedding in alternating group graphs with faulty elements. In Advanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013 (Lecture Notes in Electrical Engineering; Vol. 260). Springer Verlag. https://doi.org/10.1007/978-94-007-7262-5_145