On the Existence of K-Partite or K^P-Free Total Domination Edge-Critical Graphs

Creator(s)

Teresa W. Haynes, East Tennessee State UniversityFollow
Michael A. Henning, University of Johannesburg
Lucas C. Van Der Merwe, University of Tennessee at Chattanooga
Anders Yeo, Royal Holloway, University of London

Document Type

Conference Proceeding

Publication Date

7-6-2011

Description

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.

Citation Information

Haynes, Teresa W.; Henning, Michael A.; Van Der Merwe, Lucas C.; and Yeo, Anders. 2011. On the Existence of K-Partite or K^P-Free Total Domination Edge-Critical Graphs. Discrete Mathematics. Vol.311(13). 1142-1149. https://doi.org/10.1016/j.disc.2010.07.018 ISSN: 0012-365X