On Fixed Edges and Edge-Reconstruction of Series-Parallel Networks |
| |
| Authors: | Hongbing Fan Yu-Liang Wu C. K. Wong |
| |
| Affiliation: | (1) Department of Computer Science, University of Victoria, Victoria BC, V8W 3P6 Canada, CA;(2) Department of Computer Science and Engineering, The Chinese University of Hong Kong. , HK;(3) Department of Computer Science and Engineering, The Chinese University of Hong Kong. e-mail: wongck@cse.cuhk.edu.hk, HK |
| |
| Abstract: | An edge e of a graph G is said to be a fixed edge if G−e+e ′≅G implies that e ′=e, and a forced edge if G−e+e ′ is an edge-reconstruction of G implies that e ′=e. In this paper, we use the method of excludable configurations to investigate the fixed edges and the forced edges of series-parallel networks. It is proved that all series-parallel networks contain fixed edges except P 3∨K 1 and P 4∨K 1, and that all series-parallel networks are edge-reconstructible. Received: December 22, 1997 Final version received: July 21, 1999 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
