On extremal weighted digraphs with no heavy paths

Binlong Li; Shenggui Zhang

doi:10.1016/j.disc.2010.01.016

On extremal weighted digraphs with no heavy paths

Binlong Li
, Shenggui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.

Original language	English
Pages (from-to)	1640-1644
Number of pages	5
Journal	Discrete Mathematics
Volume	310
Issue number	10-11
DOIs	https://doi.org/10.1016/j.disc.2010.01.016
State	Published - 6 Jun 2010

Keywords

Extremal graphs
Heavy paths
Weighted digraphs

Access to Document

10.1016/j.disc.2010.01.016

Cite this

@article{c51a589b92d14445ae7f7c121efd9502,

title = "On extremal weighted digraphs with no heavy paths",

abstract = "Bollob{\'a}s and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.",

keywords = "Extremal graphs, Heavy paths, Weighted digraphs",

author = "Binlong Li and Shenggui Zhang",

year = "2010",

month = jun,

day = "6",

doi = "10.1016/j.disc.2010.01.016",

language = "英语",

volume = "310",

pages = "1640--1644",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10-11",

}

TY - JOUR

T1 - On extremal weighted digraphs with no heavy paths

AU - Li, Binlong

AU - Zhang, Shenggui

PY - 2010/6/6

Y1 - 2010/6/6

N2 - Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.

AB - Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.

KW - Extremal graphs

KW - Heavy paths

KW - Weighted digraphs

UR - https://www.scopus.com/pages/publications/77949286889

U2 - 10.1016/j.disc.2010.01.016

DO - 10.1016/j.disc.2010.01.016

M3 - 文章

AN - SCOPUS:77949286889

SN - 0012-365X

VL - 310

SP - 1640

EP - 1644

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10-11

ER -

On extremal weighted digraphs with no heavy paths

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this