𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Total dominating functions in trees: Minimality and convexity

✍ Scribed by E. J. Cockayne; C. M. Mynhardt; Bo Yu

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
380 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A total dominating function (TDF) of a graph G = (V, E) is a function f: V ← [0, 1] such that for each v Ο΅ V, Ξ£~uΟ΅N(v)~ f(u) β‰₯ 1 (where N(v) denotes the set of neighbors of vertex v). Convex combinations of TDFs are also TDFs. However, convex combinations of minimal TDFs (i.e., MTDFs) are not necessarily minimal.

In this paper we discuss the existence in trees of a universal MTDF (i.e., an MTDF whose convex combinations with any other MTDF are also minimal). Β© 1995 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

Convexity of minimal total dominating fu
Convexity of minimal total dominating functions in graphs
✍ Yu, Bo πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 122 KB πŸ‘ 2 views

A total dominating function (TDF) of a graph G = (V, E) is a function f : V β†’ [0, 1] such that for each v ∈ V , the sum of f values over the open neighbourhood of v is at least one. Zero-one valued TDFs are precisely the characteristic functions of total dominating sets of G. We study the convexity

Scaling limits for minimal and random sp
Scaling limits for minimal and random spanning trees in two dimensions
✍ Michael Aizenman; Almut Burchard; Charles M. Newman; David B. Wilson πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 469 KB

A general formulation is presented for continuum scaling limits of stochastic spanning trees. A spanning tree is expressed in this limit through a consistent collection of subtrees, which includes a tree for every finite set of endpoints in ‫ޒ‬ d . Tightness of the distribution, as ␦ Βͺ 0, is establi