𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Total domination in graphs with minimum degree three

✍ Scribed by Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
132 KB
Volume
34
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ t (G) ≤ 7n/13.

📜 SIMILAR VOLUMES

Bounds related to domination in graphs w
Bounds related to domination in graphs with minimum degree two
✍ Sanchis, Laura A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 2 views

A dominating set for a graph G = (V, E) is a subset of vertices V ⊆ V such that for all v ∈ V -V there exists some u ∈ V for which {v, u} ∈ E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q e

Total interval number for graphs with bo
Total interval number for graphs with bounded degree
✍ Kostochka, Alexander V.; West, Douglas B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 1 views

The total interval number of an n-vertex graph with maximum degree ∆ is at most (∆+1/∆)n/2, with equality if and only if every component of the graph is K ∆,∆ . If the graph is also required to be connected, then the maximum is ∆n/2 + 1 when ∆ is even, but when ∆ is odd it exceeds [∆ + 1/(2.5∆ + 7.7

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

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 👁 1 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