Hamiltonian Laceability of Spider Web Networks

蜘蛛網型網路的漢米爾連通性

10.6358/JCYU.200503.0001

高欣欣(Shin-Shin Kao)；徐力行(Lih-Hsing Hsu)

漢米爾連通性 ； 漢米爾 ； hamiltonian laceable ； hamiltonian

中原學報

33卷1期（2005 / 03 / 01）

1 - 10

英文

本文證明新近所提出的二部圖，蜘蛛網型網路，擁有漢米爾連通性。更具體地說，設G＝(V,E)是一個蜘蛛網型網路的圖形，其中V＝C∪D且C與D爲它的二個分部點集。則給定任意一對點{x,y}使得x∈C，y∈D，G中必有一條路逕連接x與y且此路逕經過V中所有點恰好一次。

In this paper, we prove the recently proposed family of bipartite graphs, Spider Web Networks [9], are hamiltonian laceable. More precisely, let G=(V, E) be a spider web network with bipartitions C and D. For any pair of nodes {x, y| x∈C, y∈D}, there is a path P between x and y where P visits all nodes in V exactly once.