𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Convexity of minimal dominating functions of trees — II

✍ Scribed by E.J. Cockayne; G. MacGillivray; C.M. Mynhardt

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
580 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The relation Ye on the set of minimal dominating functions (MDFs) of a finite graph G is defined by f&?g if and only if any convex combination off and g is also an MDF. If fis a nonintegral MDF of a tree, the existence of another MDF with fewer nonintegral values and other desirable properties is established. This existence theorem is then used to obtain facts about the relation W. In particular, we deduce that if a tree T has a universal MDF (i.e. an MDF g such that f9g for all MDFsf ), then Thas a universal MDF with only integral values. Further, results concerning the convexity graph of the MDFs of a tree (a graph which exhibits the essential properties of the relation W) are obtained.

📜 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

Universal minimal total dominating funct
Universal minimal total dominating functions of trees
✍ Alan Stacey 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We show that any tree that has a universal minimal total dominating function has one which only takes 0-1 values. K 3 demonstrates that this fails for graphs in general. Given a graph G =(V, E), for each vertex ve V let F(v) be the set of its neighbours (in particular, not including v itself). A to

Total dominating functions in trees: Min
Total dominating functions in trees: Minimality and convexity
✍ E. J. Cockayne; C. M. Mynhardt; Bo Yu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 380 KB

## 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

A characterisation of universal minimal
A characterisation of universal minimal total dominating functions in trees
✍ E.J. Cockayne; C.M. Mynhardt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 445 KB

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~Ntv)f(u)>~ 1, where N(v) denotes the set of neighbours of v. Although convex combinations of TDFs are also TDFs, convex combinations of minimal TDFs (MTDFs) are not necessarily minimal. An