<abstract xmlns="http://www.w3.org/1999/xhtml"><p> A [1; 2]-set S in a graph G is a vertex subset such that every vertex not in S has at least one and at most two neighbors in it. If the additional requirement that the set be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we provide local conditions, depending on the degree of vertices, for the existence of independent [1; 2]-sets in caterpillars. We also study the relationship between independent [1; 2]-sets and independent dominating sets in this graph class, that allows us to obtain an upper bound for the associated parameter, the independent [1; 2]-number, in terms of the independent domination number.</p></abstract>

A [1; 2]-set S in a graph G is a vertex subset such that every vertex not in S has at least one and at most two neighbors in it. If the additional requirement that the set be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we provide local conditions, depending on the degree of vertices, for the existence of independent [1; 2]-sets in caterpillars. We also study the relationship between independent [1; 2]-sets and independent dominating sets in this graph class, that allows us to obtain an upper bound for the associated parameter, the independent [1; 2]-number, in terms of the independent domination number.

Independent [1,2]-number versus independent domination number

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Independent [1,2]-number versus independent domination number"}

A [1; 2]-set S in a graph G is a vertex subset such that every vertex not in S has at least one and at most two neighbors in it. If the additional requirement...

Independent [1,2]-number versus independent domination number

Publicado en línea: 31 mar 2018

Páginas: 5 - 24

Recibido: 22 nov 2016

Aceptado: 29 nov 2016

DOI: https://doi.org/10.1515/auom-2017-0031

Palabras clave
graph, domination, independence, caterpillar

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Independent [1,2]-number versus independent domination number

Publicado en línea: 31 mar 2018

Páginas: 5 - 24

Recibido: 22 nov 2016

Aceptado: 29 nov 2016

DOI: https://doi.org/10.1515/auom-2017-0031

Palabras clavegraph, domination, independence, caterpillar

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Palabras clave
graph, domination, independence, caterpillar