On the existence of k-partite or Kp-free total domination edge-critical graphs

Autor:	Anders Yeo, Michael A. Henning, Teresa W. Haynes, Lucas C. van der Merwe
Rok vydání:	2011
Předmět:	Combinatorics Discrete mathematics Vertex-transitive graph Graph power Symmetric graph Neighbourhood (graph theory) Discrete Mathematics and Combinatorics Multipartite graph Bound graph Graph toughness Complement graph Theoretical Computer Science Mathematics
Zdroj:	Discrete Mathematics. 311:1142-1149
ISSN:	0012-365X
DOI:	10.1016/j.disc.2010.07.018
Popis:	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 @c"t(G). The graph G is 3"t-critical if @c"t(G)=3 and @c"t(G+e)=2 for every edge e in the complement of G. We show that no bipartite graph is 3"t-critical. The tripartite 3"t-critical graphs are characterized. For every k>=3, we prove that there are only a finite number of 3"t-critical k-partite graphs. We show that the 5-cycle is the only 3"t-critical K"3-free graph and that there are only a finite number of 3"t-critical K"4-free graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::343ef13ee95b371ab684e04f7d6de031 https://doi.org/10.1016/j.disc.2010.07.018 Zobrazit plný text záznamu Full Text from ScienceDirect