<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

Publié en ligne: 31 mars 2018

Pages: 5 - 24

Reçu: 22 nov. 2016

Accepté: 29 nov. 2016

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

Mots clés
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

Publié en ligne: 31 mars 2018

Pages: 5 - 24

Reçu: 22 nov. 2016

Accepté: 29 nov. 2016

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

Mots clésgraph, domination, independence, caterpillar

© 2018

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

Mots clés
graph, domination, independence, caterpillar