Hamiltonian-laceability of star graphs

Sun-Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to conferencePaper

6 Citations (Scopus)

Abstract

Suppose G is a bipartite graph with two partite sets of equal size. G is said to be strongly hamiltonian-laceable if there is a hamiltonian path between every two vertices that belong to different partite sets, and there is a path of (maximal) length N-2 between every two vertices that belong to the same partite set, where N is the order of G. The star graph is known to be bipartite. In this paper, we show that the n-dimensional star graph, where n≥4 is strongly hamiltonian-laceable.

Original languageEnglish
Pages112-117
Number of pages6
DOIs
Publication statusPublished - 1997 Jan 1
Event3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan
Duration: 1997 Dec 181997 Dec 20

Conference

Conference3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
CountryTaiwan
CityTaipei
Period97-12-1897-12-20

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'Hamiltonian-laceability of star graphs'. Together they form a unique fingerprint.

  • Cite this

    Hsieh, S-Y., Chen, G. H., & Ho, C. W. (1997). Hamiltonian-laceability of star graphs. 112-117. Paper presented at 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997, Taipei, Taiwan. https://doi.org/10.1002/1097-0037(200012)36