Isolation Number versus Domination Number of Trees

Abstract

If G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G). In this paper, we analyze a family of trees T where ι(T)=γ(T), and we prove that ι(T)=n3 implies ι(T)=γ(T). Moreover, we give different equivalent characterizations of such graphs and we propose simple algorithms to build these trees from the connections of stars.

Keywords

• domination number
• isolation number
• trees
• algorithms