On the total domination subdivision number in some classes of graphs |
| |
Authors: | O. Favaron H. Karami R. Khoeilar S. M. Sheikholeslami |
| |
Affiliation: | 1.LRI UMR 8623,Univ. Paris Sud and CNRS,Orsay,France;2.Department of Mathematics,Azarbaijan University of Tarbiat Moallem,Tabriz,Iran |
| |
Abstract: | A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdgt(G)mathrm {sd}_{gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sdgt(G) £ gt(G)+1mathrm {sd}_{gamma_{t}}(G)leqgamma_{t}(G)+1 for some classes of graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|