Isolation Number versus Domination Number of Trees
Ver/ abrir
Use este enlace para citar
http://hdl.handle.net/2183/28498
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución 4.0 Internacional (CC BY 4.0)
Coleccións
- GI-XDA - Artigos [8]
- GI-GTEC - Artigos [186]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Isolation Number versus Domination Number of TreesAutor(es)
Data
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
Resumo
[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 chave
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 do editor
Dereitos
Atribución 4.0 Internacional (CC BY 4.0)
ISSN
2227-7390