On average edge length of minimum spanning trees

Authors
Nath, SK Chowdhury, RA Kaykobad, M
Citation
Sk. Nath et al., On average edge length of minimum spanning trees, INF PROCESS, 70(5), 1999, pp. 241-243
Citations number
4
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
70
Issue
5
Year of publication
1999
Pages
241 - 243
Database
ISI
SICI code
0020-0190(19990621)70:5<241:OAELOM>2.0.ZU;2-J
Abstract
This paper presents a theorem that asserts that average edge length of the minimum spanning tree of a complete graph on n + 1 vertices is less than or equal to the average edge length of all the n + 1 minimum spanning trees o f the induced graph on n vertices. The result is also in compliance with re sults given by Frieze and Steele. (C) 1999 Elsevier Science B.V. All rights reserved.