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, 2020 at 18:10
  • $\begingroup$ could you explain in more detail? Thanks $\endgroup$
    – mclarenp1
    Apr 19, 2020 at 18:25
  • $\begingroup$ Just giving you a search phrase because AFAIK dude set is nonstandard nomenclature. $\endgroup$
    – RobPratt
    Apr 19, 2020 at 18:31

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .