Return to search

On the Existence of K-Partite or K<sup>P</sup>-Free Total Domination Edge-Critical Graphs

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 3t-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 3t-critical. The tripartite 3 t-critical graphs are characterized. For every k<3, we prove that there are only a finite number of 3t-critical k-partite graphs. We show that the 5-cycle is the only 3t-critical K3-free graph and that there are only a finite number of 3t-critical K4-free graphs.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-17608
Date06 July 2011
CreatorsHaynes, Teresa W., Henning, Michael A., Van Der Merwe, Lucas C., Yeo, Anders
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0018 seconds