## Abstract

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3_{t}EC graph is a total domination edge-critical graph with total domination number 3 and a 3_{t}VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G - v has a perfect matching for every vertex v in G. In this paper, we show that every 3_{t}EC graph of even order has a perfect matching, while every 3_{t}EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3_{t}VC graph of even order that is K_{1,7}-free has a perfect matching, while every 3_{t}VC graph of odd order that is K_{1,6}-free is factor-critical. We show that these results are tight in the sense that there exist 3_{t}VC graphs of even order with no perfect matching that are K_{1,8}-free and 3_{t}VC graphs of odd order that are K_{1,7}-free but not factor-critical.

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

Pages (from-to) | 685-701 |

Number of pages | 17 |

Journal | Graphs and Combinatorics |

Volume | 27 |

Issue number | 5 |

DOIs | |

Publication status | Published - Sept 2011 |

## Keywords

- Edge-critical
- Factor-critical
- Perfect matching
- Total domination
- Vertex-critical

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics