Cycles in weighted graphs |
| |
Authors: | J. A. Bondy Genghua Fan |
| |
Affiliation: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Department of Mathematics, Arizona State University, 85 287 Tempe, AZ, U.S.A. |
| |
Abstract: | A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4]. |
| |
Keywords: | 05 C 35 05 C 38 |
本文献已被 SpringerLink 等数据库收录! |
|