Isolation Number versus Domination Number of Trees

Mathematics

Francisco J. Vazquez-Araujo¹  Adriana Dapena¹  Magdalena Lemańska²  María José Souto-Salorio³ 

[1] CITIC Research Center, University of A Coruña, Campus de Elviña, 15071 A Coruña, Spain;Department of Technical Physics and Applied Mathematics, Gdansk University of Technology, ul. Narutowicza 11/12, 80-233 Gdansk, Poland;Differential Geometry and Its Applcations Research Group, University of A Coruña, Campus de Elviña, 15071 A Coruña, Spain;

关键词: domination number;    isolation number;    trees;    algorithms;   

DOI  :  10.3390/math9121325

来源: DOAJ

【 摘 要 】

If $G=(V_G,E_G)$ is a graph of order n, we call $S\subseteq V_G$ an isolating set if the graph induced by $V_G-N_G\left[S\right]$ contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by $\iota \left(G\right).$ It is known that $\iota \left(G\right)\le \frac{n}{3}$ and the bound is sharp. A subset $S\subseteq V_G$ is called dominating in G if $N_G\left[S\right]=V_G$. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by $\gamma \left(G\right).$ In this paper, we analyze a family of trees T where $\iota \left(T\right)=\gamma \left(T\right)$, and we prove that $\iota \left(T\right)=\frac{n}{3}$ implies $\iota \left(T\right)=\gamma \left(T\right).$ Moreover, we give different equivalent characterizations of such graphs and we propose simple algorithms to build these trees from the connections of stars.

【 授权许可】

Unknown