4
$\begingroup$

Let $G$ be a graph and let $V$ be a set of vertices with the following property: If a vertex $v$ is connected to every $u\in V$, then $v$ has to be in $V$. Does such $V$ have a (standard) name? Note that $V$ may not be a maximal clique, since it may happen that the induced graph on $V$ is not complete.

$\endgroup$
  • 1
    $\begingroup$ It seems to me like you can take any set of nodes $V_0$ and let $V_n$ be the union of $V_{n-1}$ with the set of nodes that are neighbour to all vertices in $V_{n-1}$. Eventually you get a set like yours. $\endgroup$ – Arthur Jun 22 '15 at 11:00
  • 1
    $\begingroup$ @Arthur Doesn't $V_1$ allready have the stated property? Let $v \in V(G)$ be connected to all vertices in $V_1$. Then $v$ is connected to all vertices in $V_0$ (as $V_0 \subseteq V_1$), hence $v \in V_1$. $\endgroup$ – martini Jun 22 '15 at 11:43
  • $\begingroup$ @martini You're right. $\endgroup$ – Arthur Jun 22 '15 at 11:46
  • $\begingroup$ It's not clear, whether the set $V$ is well-defined... $\endgroup$ – DVD Jun 24 '15 at 0:15
0
$\begingroup$

You can use the definition of simplical vertices. A simplical vertex $v$ is a vertex whose neighbors $N(v)$ form a clique. Thus, the set of vertices $V =\{v\} \cup N(v)$ is the set that you are interested in.

$\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.