Premium
Topological properties of incomplete WK‐recursive networks
Author(s) -
Su MingYang,
Chen GenHuey,
Duh DyiRong
Publication year - 1998
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/(sici)1097-0037(199808)32:1<23::aid-net3>3.0.co;2-l
Subject(s) - hamiltonian (control theory) , hamiltonian path , mathematics , topology (electrical circuits) , path (computing) , computer science , combinatorics , algorithm , discrete mathematics , mathematical optimization , graph , programming language
Recently, WK‐recursive networks have received much attention due to their many favorable properties. However, they suffered from a rigorous restriction on their sizes. Incomplete WK‐recursive networks were proposed to relieve this restriction. In this paper, the topological properties of incomplete WK‐recursive networks are investigated. It is shown that they contain Hamiltonian cycles if their connectivities are greater than one. A sufficient and necessary condition is also proposed for those with connectivity one to contain a Hamiltonian path. A linear‐time algorithm using the prune‐and‐search technique is presented to compute their diameters. © 1998 John Wiley & Sons, Inc. Networks 32: 23–45, 1998