The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures

A polytope P ⊆ [ 0 , 1 ] n is said to have the persistency property if for every vector c ∈ R n and every c -optimal point x ∈ P , there exists a c -optimal integer point y ∈ P ∩ { 0 , 1 } n such that x i = y i for each i ∈ { 1 , … , n } with x i ∈ { 0 , 1 } . In this paper, we consider a relaxation of the persistency property called 1-persistency . We study the family Q of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as Q - persistent graphs. We provide sufficient conditions for a graph to be Q -persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of ( k , U ) -umbrella graphs, and study which of them belong to Q . The property of being Q -persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family Q , i.e., minimally not Q -persistent (mn Q ) graphs. In this line, we identify some mn Q ( k , U ) -umbrella graphs and also other forbidden minimal structures for Q -persistency outside this family (named as whale graphs).