Hamiltonian-laceability of star graphs

Sun Yuan Hsieh; Gen Huey Chen; Chin Wen Ho

doi:10.1002/1097-0037(200012)36

Hamiltonian-laceability of star graphs

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Department of Computer Science and Information Engineering

Research output: Contribution to conference › Paper › peer-review

7 Scopus citations

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 language	English
Pages	112-117
Number of pages	6
DOIs	https://doi.org/10.1002/1097-0037(200012)36
State	Published - 1997
Event	3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan Duration: 18 Dec 1997 → 20 Dec 1997

Conference

Conference	3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
Country/Territory	Taiwan
City	Taipei
Period	18/12/97 → 20/12/97

Access to Document

10.1002/1097-0037(200012)36

Cite this

@conference{bf23bd33446f4c598208e0c7b8ed1536,

title = "Hamiltonian-laceability of star graphs",

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.",

author = "Hsieh, {Sun Yuan} and Chen, {Gen Huey} and Ho, {Chin Wen}",

note = "Publisher Copyright: {\textcopyright} 1997 IEEE.; 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 ; Conference date: 18-12-1997 Through 20-12-1997",

year = "1997",

doi = "10.1002/1097-0037(200012)36",

language = "???core.languages.en_GB???",

pages = "112--117",

}

TY - CONF

T1 - Hamiltonian-laceability of star graphs

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

AU - Ho, Chin Wen

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883661207&partnerID=8YFLogxK

U2 - 10.1002/1097-0037(200012)36

DO - 10.1002/1097-0037(200012)36

M3 - 會議論文

AN - SCOPUS:84883661207

SP - 112

EP - 117

T2 - 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997

Y2 - 18 December 1997 through 20 December 1997

ER -

Hamiltonian-laceability of star graphs

Abstract

Conference

Access to Document

Fingerprint

Cite this