Certified Hop Independence: Properties and Connections with other Variants of Independence
DOI:
https://doi.org/10.29020/nybg.ejpam.v17i1.5044Keywords:
Hop Independence , Certified Hop Independent set, Certified Hop Independence numberAbstract
Let G be a graph. Then B ⊆ V (G) is called a certified hop independent set of G if for every a, b ∈ B, dG(a, b) ̸= 2 and for every x ∈ B has either zero or at least two neighbors in V (G) \ B. The maximum cardinality among all certified hop independent sets in G, denoted by αch(G), is called the certified hop independence number of G. In this paper, we initiate the study of certified hop independence in graphs and we establish some of its properties. We give realization results involving hop independence and certified hop independence parameters, and we show that the difference between these two parameters can be made arbitrarily large. We characterize certified hop independent sets in some graphs and we use these results to obtain the exact values or bounds of the parameter. Moreover, we show that the certified hop independence and independence parameters are incomparable.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 European Journal of Pure and Applied Mathematics
![Creative Commons License](http://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Upon acceptance of an article by the journal, the author(s) accept(s) the transfer of copyright of the article to European Journal of Pure and Applied Mathematics.
European Journal of Pure and Applied Mathematics will be Copyright Holder.