<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

Data publikacji: 31 mar 2018

Zakres stron: 5 - 24

Otrzymano: 22 lis 2016

Przyjęty: 29 lis 2016

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

Słowa kluczowe
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

Data publikacji: 31 mar 2018

Zakres stron: 5 - 24

Otrzymano: 22 lis 2016

Przyjęty: 29 lis 2016

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

Słowa kluczowegraph, domination, independence, caterpillar

© 2018

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

Słowa kluczowe
graph, domination, independence, caterpillar