A New Bound on the Total Domination Subdivision Number |
| |
Authors: | O Favaron H Karami R Khoeilar S M Sheikholeslami |
| |
Institution: | (1) Univ Paris-Sud, LRI, UMR 8623, Orsay, F-91405, France;(2) Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, I.R. 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
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 for every simple
connected graph G of order n ≥ 3,
where d
2(v) is the number of vertices of G at distance 2 from v.
R. Khoeilar: Research supported by the Research Office of Azarbaijan University of Tarbiat Moallem. |
| |
Keywords: | Total domination number Total domination subdivision number |
本文献已被 SpringerLink 等数据库收录! |
|