## Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ^{γt}(G). The graph G is 3_{t}-critical if ^{γt}(G)=3 and ^{γt}(G+e)=2 for every edge e in the complement of G. We show that no bipartite graph is 3_{t}-critical. The tripartite 3 _{t}-critical graphs are characterized. For every k<3, we prove that there are only a finite number of 3_{t}-critical k-partite graphs. We show that the 5-cycle is the only 3_{t}-critical ^{K3}-free graph and that there are only a finite number of 3_{t}-critical ^{K4}-free graphs.

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

Pages (from-to) | 1142-1149 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 311 |

Issue number | 13 |

DOIs | |

Publication status | Published - 6 Jul 2011 |

## Keywords

- Diameter critical
- Multipartite graph
- Total domination edge-critical

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'On the existence of k-partite or K^{p}-free total domination edge-critical graphs'. Together they form a unique fingerprint.