Journal Title
Title of Journal: Graphs and Combinatorics
|
Abbravation: Graphs and Combinatorics
|
|
|
|
|
|
|
|
Authors: Michael A Henning Anders Yeo
Publish Date: 2010/12/18
Volume: 27, Issue: 5, Pages: 685-701
Abstract
A graph is total domination edgecritical if the addition of any edge decreases the total domination number while a graph with minimum degree at least two is total domination vertexcritical if the removal of any vertex decreases the total domination number A 3 t EC graph is a total domination edgecritical graph with total domination number 3 and a 3 t VC graph is a total domination vertexcritical graph with total domination number 3 A graph G is factorcritical 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 cutvertex is factorcritical We also show that every 3 t VC graph of even order that is K 17free has a perfect matching while every 3 t VC graph of odd order that is K 16free is factorcritical 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 18free and 3 t VC graphs of odd order that are K 17free but not factorcritical
Keywords:
.
|
Other Papers In This Journal:
|