Total Domination in Partitioned Graphs |
| |
| Authors: | Allan Frendrup Preben Dahl Vestergaard Anders Yeo |
| |
| Institution: | (1) Department of Mathematical Sciences, Aalborg University, Aalborg, Denmark;(2) Department of Computer Science, University of London, Royal Holloway, Surrey, UK |
| |
| Abstract: | We present results on total domination in a partitioned graph G = (V, E). Let γ
t
(G) denote the total dominating number of G. For a partition  , k ≥ 2, of V, let γ
t
(G; V
i
) be the cardinality of a smallest subset of V such that every vertex of V
i
has a neighbour in it and define the following
We summarize known bounds on γ
t
(G) and for graphs with all degrees at least δ we derive the following bounds for f
t
(G; k) and g
t
(G; k).
| (i) |
For δ ≥ 2 and k ≥ 3 we prove f
t
(G; k) ≤ 11|V|/7 and this inequality is best possible.
|
| (ii) |
for δ ≥ 3 we prove that f
t
(G; 2) ≤ (5/4 − 1/372)|V|. That inequality may not be best possible, but we conjecture that f
t
(G; 2) ≤ 7|V|/6 is.
|
| (iii) |
for δ ≥ 3 we prove f
t
(G; k) ≤ 3|V|/2 and this inequality is best possible.
|
| (iv) |
for δ ≥ 3 the inequality g
t
(G; k) ≤ 3|V|/4 holds and is best possible.
|
|
| |
| Keywords: | Total domination Partitions and Hypergraphs |
| 本文献已被 SpringerLink 等数据库收录！ |
|
