Have a personal or library account? Click to login
Independent [1,2]-number versus independent domination number Cover

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.

DOI: https://doi.org/10.1515/auom-2017-0031 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784
Language: English
Page range: 5 - 24
Submitted on: Nov 22, 2016
Accepted on: Nov 29, 2016
Published on: Mar 31, 2018
Published by: Ovidius University of Constanta
In partnership with: Paradigm Publishing Services
Publication frequency: 3 issues per year

© 2018 Sahar A. Aleid, Mercè Mora, María Luz Puertas, published by Ovidius University of Constanta
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.