Name
Abstract | ||
|---|---|---|
A weighted graph is one in which each edge e is assigned a nonnegative number w(e), called the weight of e. The weight w(G) of a weighted graph G 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 on n vertices contains a cycle of weight at least 2w(G)/(n - 1). Furthermore, we completely characterize the 2-edge-connected weighted graphs on n vertices that contain no cycle of weight more than 2w(G)/(n - 1). This generalizes, to weighted graphs, a classical result of Erdos and Gallai [4]. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BF01205072 | COMBINATORICA |
Field | DocType | Volume |
Graph theory,Discrete mathematics,Graph,Combinatorics,Weighting,Vertex (geometry),Chordal graph,Cycle graph,Mathematics | Journal | 11 |
Issue | ISSN | Citations |
3 | 0209-9683 | 11 |
PageRank | References | Authors |
1.61 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. A. Bondy | 1 | 11 | 1.61 |
| Genghua Fan | 2 | 412 | 65.22 |