Isolation Number versus Domination Number of Trees
Ver/Abrir
Use este enlace para citar
http://hdl.handle.net/2183/28498
Excepto si se señala otra cosa, la licencia del ítem se describe como Atribución 4.0 Internacional (CC BY 4.0)
Colecciones
- GI-XDA - Artigos [13]
- GI-GTEC - Artigos [190]
Metadatos
Mostrar el registro completo del ítemTítulo
Isolation Number versus Domination Number of TreesAutor(es)
Fecha
2021-06Cita bibliográfica
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
Resumen
[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.
Palabras clave
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
Versión del editor
Derechos
Atribución 4.0 Internacional (CC BY 4.0)
ISSN
2227-7390