We provide sufficient conditions for a graph to belong to $\mathcal{Q}$, and identify several graph classes of this family. We introduce the family of graphs called $(k,U)$-umbrella graphs, and study which members of this family belong to $\mathcal{Q}$. The property of being $\mathcal{Q}$-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for not having this property, defined as \emph{minimally not $\mathcal{Q}$-persistent} (mn$\mathcal{Q}$) graphs. In this line, we identify some mn$\mathcal{Q}$ $(k,U)$-umbrella graphs and also other forbidden minimal structures for $\mathcal{Q}$-persistency outside this family (named as \emph{whale} graphs). We conclude the paper by suggesting an interesting future line of work about the persistency-preservation property of valid inequalities and its potential practical applications.
The 1-persistency of the clique relaxation of the stable set polytope: a focus on some forbidden structures
\(\)
A polytope $P\subseteq [0,1]^n$ is said to have the \emph{persistency} property if for every vector $c\in \R^{n}$ and every $c$-optimal point $x\in P$, there exists a $c$-optimal integer point $y\in P\cap \{0,1\}^n$ such that $x_i = y_i$ for each $i \in \{1,\dots,n\}$ with $x_i \in \{0,1\}$. In this paper, we consider a relaxation of the persistency property called 1-persistency, over the clique relaxation of the stable set polytope in graphs. In particular, we study the family $\mathcal{Q}$ of graphs whose clique relaxation of the stable set polytope has 1-persistency.
We provide sufficient conditions for a graph to belong to $\mathcal{Q}$, and identify several graph classes of this family. We introduce the family of graphs called $(k,U)$-umbrella graphs, and study which members of this family belong to $\mathcal{Q}$. The property of being $\mathcal{Q}$-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for not having this property, defined as \emph{minimally not $\mathcal{Q}$-persistent} (mn$\mathcal{Q}$) graphs. In this line, we identify some mn$\mathcal{Q}$ $(k,U)$-umbrella graphs and also other forbidden minimal structures for $\mathcal{Q}$-persistency outside this family (named as \emph{whale} graphs). We conclude the paper by suggesting an interesting future line of work about the persistency-preservation property of valid inequalities and its potential practical applications.
We provide sufficient conditions for a graph to belong to $\mathcal{Q}$, and identify several graph classes of this family. We introduce the family of graphs called $(k,U)$-umbrella graphs, and study which members of this family belong to $\mathcal{Q}$. The property of being $\mathcal{Q}$-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for not having this property, defined as \emph{minimally not $\mathcal{Q}$-persistent} (mn$\mathcal{Q}$) graphs. In this line, we identify some mn$\mathcal{Q}$ $(k,U)$-umbrella graphs and also other forbidden minimal structures for $\mathcal{Q}$-persistency outside this family (named as \emph{whale} graphs). We conclude the paper by suggesting an interesting future line of work about the persistency-preservation property of valid inequalities and its potential practical applications.