# polytopes and integer programming

Given a connected graph $$G$$ with vertex set $$V(G)$$, a set $$S\subseteq V(G)$$ is called a dude set if every vertex of $$V(G)\setminus S$$ is adjacent to at least one vertex of $$S$$. Let $$\mathcal{D}$$ denote the collection of all dude sets of G. As usual, the $$0-1$$ vector $$x(S)\in \mathbb{Z}^{V(G)}$$ with $$x_u(S)=1$$ if $$u\in S$$ and $$x_u(S)=0$$ if $$u\neq S$$ is called the characteristic vector of $$S$$. The convex hull of the set $$\{x(S):S\in D\}$$, denoted by $$P_{\mathcal{D}}$$, is called the dude-set polytope of $$G$$. If $$u\in V(G)$$ is a vertex of $$G$$, the neighborhood of $$u$$ in $$G$$, denoted by $$N(u)$$, is the set consisting of $$u$$ together with the vertices that are adjacent to $$u$$ in $$G$$.

(a) Prove that $$P_{\mathcal{D}}$$ has dimension $$|V(G)|$$

(b) Suppose that $$u$$ is any vertex of $$G$$. Prove that the inequality $$x_u\leq 1$$ describe a facet of $$P_{\mathcal{D}}$$.

(c) Suppose that $$u$$ is any vertex of $$G$$. Suppose that $$|N(u)|\geq 3$$ for every $$v\in N(u)$$. Prove that the inequality $$x_u\geq 0$$ describes a facet of $$P_{\mathcal{D}}$$.

(d) Assume now that $$G=G_n$$, a cycle on $$n$$ vertices (with no other edges other than $$n$$ edges of the cycle itself). Prove that the cycle inequality $$$$\sum_{v\in V(C_n)}x_v\geq \lceil\frac{n}{3}\rceil$$$$ is valid for $$P_{\mathcal{D}}$$, and moreover, when $$n>3$$, that it describes a facet of $$P_{\mathcal{D}}$$ if and only if $$n$$ is not a multiple of $$3$$.($$\lceil z \rceil$$ denotes the least integer greater than or equal to $$z$$)

Any ideas or thoughts will be greatly appreciated!

• dominating set Apr 19 '20 at 18:10
• could you explain in more detail? Thanks Apr 19 '20 at 18:25
• Just giving you a search phrase because AFAIK dude set is nonstandard nomenclature. Apr 19 '20 at 18:31

Some hints: For (a) and (b) it is helpful to know that the vectors $$(0, 1, 1, 1, \dots 1), (1, 0, 1, 1, \dots 1), (1, 1, 0, 1, \dots 1), \dots, (1, 1, 1, 1, \dots, 0)$$ are linearly independent. For (b), let $$H$$ be the hyperplane $$x_u = 1$$. What is the definition of a facet in terms of $$P_D \cap H$$? For (c), probably a similar idea as in (b) leads to success, but I didn't think it through yet.