Premium
Hamiltonian‐laceability of star graphs
Author(s) -
Hsieh SunYuan,
Chen GenHuey,
Ho ChinWen
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200012)36:4<225::aid-net3>3.0.co;2-g
Subject(s) - combinatorics , hamiltonian path , bipartite graph , mathematics , hamiltonian (control theory) , hamiltonian path problem , graph , discrete mathematics , mathematical optimization
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. © 2000 john Wiley & Sons, Inc.