Hamiltonian-laceability of star graphs

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to journalArticlepeer-review

87 Citations (Scopus)


Suppose that G is a bipartite graph with its 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. In other words, a strongly Hamiltonian-laceable graph has a longest path between every two of its vertices. In this paper, we show that the star graphs with dimension four or larger are strongly Hamiltonian-laceable.

Original languageEnglish
Pages (from-to)225-232
Number of pages8
Issue number4
Publication statusPublished - 2000 Dec

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


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

Cite this