Hamiltonian-laceability of star graphs

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to journalArticlepeer-review

87 Scopus citations


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
StatePublished - Dec 2000


  • Bipartite graph
  • Hamiltonian path
  • Hamiltonian-laceability
  • Longest path
  • Star graph


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

Cite this