Greedy Trees and the Extremal Distances

Hua Wang

Greedy Trees and the Extremal Distances

Mathematical Sciences

Research output: Contribution to conference › Presentation

Abstract

<div class="line" id="line-5"> We show a “universal property’ of the greedy tree with a given degree sequence, namely that the number of pairs of vertices whose distance is at most k is maximized by the greedy tree for all k. This rather strong assertion immediately implies, and is equivalent to, the minimality of the greedy trees with respect to graph invariants of the</div><div class="line" id="line-15"> form Wf (T)= Σ{u,v}&sube;V (T ) f(d(u, v)) for any nonnegative, nondecreasing function f. With di&fflig;erent choices of f, one directly solves the minimization problems of distance-based graph invariants including the classical Wiener index, the Hyper-Wiener index and the generalized Wiener index.</div>

Original language	American English
State	Published - Jun 18 2012
Event	Society for Industrial and Applied Mathematics Conference on Discrete Mathematics (SIAM-DM) - Duration: Jun 6 2016 → …

Conference

Conference	Society for Industrial and Applied Mathematics Conference on Discrete Mathematics (SIAM-DM)
Period	06/6/16 → …

Disciplines

Mathematics

Keywords

Extremal distances
Greedy trees

Cite this

@conference{fc0bd2d969a244efb47b2f594436127e,

title = "Greedy Trees and the Extremal Distances",

abstract = " We show a “universal property’ of the greedy tree with a given degree sequence, namely that the number of pairs of vertices whose distance is at most k is maximized by the greedy tree for all k. This rather strong assertion immediately implies, and is equivalent to, the minimality of the greedy trees with respect to graph invariants of the form Wf (T)= Σ{u,v}&sube;V (T ) f(d(u, v)) for any nonnegative, nondecreasing function f. With di&fflig;erent choices of f, one directly solves the minimization problems of distance-based graph invariants including the classical Wiener index, the Hyper-Wiener index and the generalized Wiener index.",

keywords = "Extremal distances, Greedy trees",

author = "Hua Wang",

year = "2012",

month = jun,

day = "18",

language = "American English",

note = "Society for Industrial and Applied Mathematics Conference on Discrete Mathematics (SIAM-DM) ; Conference date: 06-06-2016",

}

TY - CONF

T1 - Greedy Trees and the Extremal Distances

AU - Wang, Hua

PY - 2012/6/18

Y1 - 2012/6/18

N2 - We show a “universal property’ of the greedy tree with a given degree sequence, namely that the number of pairs of vertices whose distance is at most k is maximized by the greedy tree for all k. This rather strong assertion immediately implies, and is equivalent to, the minimality of the greedy trees with respect to graph invariants of the form Wf (T)= Σ{u,v}&sube;V (T ) f(d(u, v)) for any nonnegative, nondecreasing function f. With di&fflig;erent choices of f, one directly solves the minimization problems of distance-based graph invariants including the classical Wiener index, the Hyper-Wiener index and the generalized Wiener index.

AB - We show a “universal property’ of the greedy tree with a given degree sequence, namely that the number of pairs of vertices whose distance is at most k is maximized by the greedy tree for all k. This rather strong assertion immediately implies, and is equivalent to, the minimality of the greedy trees with respect to graph invariants of the form Wf (T)= Σ{u,v}&sube;V (T ) f(d(u, v)) for any nonnegative, nondecreasing function f. With di&fflig;erent choices of f, one directly solves the minimization problems of distance-based graph invariants including the classical Wiener index, the Hyper-Wiener index and the generalized Wiener index.

KW - Extremal distances

KW - Greedy trees

UR - http://www.siam.org/meetings/dm12/dm12_abstracts.pdf

M3 - Presentation

T2 - Society for Industrial and Applied Mathematics Conference on Discrete Mathematics (SIAM-DM)

Y2 - 6 June 2016

ER -

Greedy Trees and the Extremal Distances

Abstract

Conference

Disciplines

Keywords

Other files and links

Fingerprint

Cite this