Return to search

The Diameter of Total Domination Vertex Critical Graphs

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γ t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-19921
Date28 September 2004
CreatorsGoddard, Wayne, Haynes, Teresa W., Henning, Michael A., Van der Merwe, Lucas C.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0016 seconds