## Abstract

Let G = (V, E) be a graph and let S ⊆ V . A set of vertices in G totally dominates S if every vertex in S is adjacent to some vertex of that set. The least number of vertices needed in G to totally dominate S is denoted by γ _{t} (G, S). When S = V, γ _{t} (G, V) is the well studied total domination number γ _{t} (G). We wish to maximize the sum γ _{t} (G) + γ _{t} (G, V _{1}) + γ _{t} (G, V _{2}) over all possible partitions V _{1}, V _{2} of V. We call this maximum sum f _{t} (G). For a graph H, we denote by H ^ P _{2} the graph obtained from H by attaching a path of length 2 to each vertex of H so that the resulting paths are vertex-disjoint. We show that if G is a tree of order n ≥ 4 and G ∉ {P_{5}, P_{6}, P_{7}, P_{10}, P_{14}, then f _{t} (G) ≤ 14n/9 with equality if and only if G {P _{9}, P _{18}} or G = (T ^{P} _{2}) ^{P} _{2} for some tree T. If G is a connected graph of order n with minimum degree at least two, we establish that f _{t} (G) ≤ 3n/2 with equality if and only if G is a cycle of order congruent to zero modulo 4.

Original language | English |
---|---|

Pages (from-to) | 385-399 |

Number of pages | 15 |

Journal | Journal of Global Optimization |

Volume | 41 |

Issue number | 3 |

DOIs | |

Publication status | Published - Jul 2008 |

Externally published | Yes |

## Keywords

- Partitioned graphs
- Total domination

## ASJC Scopus subject areas

- Computer Science Applications
- Management Science and Operations Research
- Control and Optimization
- Applied Mathematics