0
$\begingroup$

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 \begin{equation} \sum_{v\in V(C_n)}x_v\geq \lceil\frac{n}{3}\rceil \end{equation} 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!

$\endgroup$
3
  • $\begingroup$ dominating set $\endgroup$
    – RobPratt
    Apr 19 '20 at 18:10
  • $\begingroup$ could you explain in more detail? Thanks $\endgroup$
    – mclarenp1
    Apr 19 '20 at 18:25
  • $\begingroup$ Just giving you a search phrase because AFAIK dude set is nonstandard nomenclature. $\endgroup$
    – RobPratt
    Apr 19 '20 at 18:31
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.