Isolation Number versus Domination Number of Trees
![Thumbnail](/dspace/bitstream/handle/2183/28498/mathematics-09-01325.pdf.jpg?sequence=5&isAllowed=y)
View/ Open
Use this link to cite
http://hdl.handle.net/2183/28498
Except where otherwise noted, this item's license is described as Atribución 4.0 Internacional (CC BY 4.0)
Collections
- GI-XDA - Artigos [13]
- GI-GTEC - Artigos [190]
Metadata
Show full item recordTitle
Isolation Number versus Domination Number of TreesAuthor(s)
Date
2021-06Citation
Lemańska, M.; Souto-Salorio, M.J.; Dapena, A.; Vazquez-Araujo, F.J. Isolation Number versus Domination Number of Trees. Mathematics 2021, 9, 1325. https://doi.org/10.3390/math9121325
Abstract
[Abstract] If 𝐺 = (Vɢ,Eɢ) is a graph of order n, we call 𝑆 ⊆ Vɢ an isolating set if the graph induced by Vɢ − Nɢ[𝑆] contains no edges. The minimum cardinality of an isolating set of 𝐺 is called the isolation number of 𝐺, and it is denoted by 𝜄(𝐺). It is known that 𝜄(𝐺) ≤ ⁿ⁄₃ and the bound is sharp.
A subset 𝑆 ⊆ Vɢ is called dominating in 𝐺 if Nɢ[𝑆] = Vɢ. The minimum cardinality of a dominating set of 𝐺 is the domination number, and it is denoted by 𝛾(𝐺). In this paper, we analyze a family of trees 𝑇 where 𝜄(𝑇) = 𝛾(𝑇), and we prove that 𝜄(T) = ⁿ⁄₃ implies 𝜄(𝑇) = 𝛾(𝑇). Moreover, we give different equivalent characterizations of such graphs and we propose simple algorithms to build these trees from the connections of stars.
Keywords
Algoritmos
Numero de dominación
Número de aislamiento
Domination number
Isolation number
Trees
Algorithms
Numero de dominación
Número de aislamiento
Domination number
Isolation number
Trees
Algorithms
Editor version
Rights
Atribución 4.0 Internacional (CC BY 4.0)
ISSN
2227-7390