ETERNAL PARAMETERS IN GRAPHS

Abstract

Let G = (V, E) be a graph and S, an independent set of G. According to what S represents an element x of this set can be out of order.
It is necessary to replace x by another vertex y ∈ V and y ∈ (V \ S) such that the new set S \ {x} ∪ {y} is an independent set of G. In this work, we present eternal independent properties, necessary and sufficient conditions so that an independent set S is eternal or secured, a process of stable securing and, finally, we give a c onstruction algorithm of an eternal maximal independent set of the graph. Also, for a transversal T, we give the necessary and sufficient co nditions so that it is secured, as well as a procedure to search for an eternal minimal transversal set in Pn and Cn.