Basically, I am looking for a (well-defined) term for some "borderline" vertexes interconnecting other vertices in and outside of a given connected component.

More specifically, given directed graph $G = (V_G, E_G)$ and (strongly) connected component $C = (V_C, E_C)$, how do people refer to such vertices $x$, where,

  1. $x \in V_C$;
  2. $\exists\ v \in V_G \setminus V_C$ such that $(x, v) \in E_G \setminus E_C$;

My friends have suggested names such as gateway vertex and border vertex. But I feel obliged to make sure we are not reinventing something well-known / well-defined.

It would be helpful if someone can help identify an equivalent (or likewise) definition of this concept in the literature. Thanks a lot.


Please note that -- unlike the well-defined concept of cut vertex -- the concept of borderline vertex (or whatever it should be called) is with respect to a specific given component, not the entire graph.

  • 1
    $\begingroup$ What is the purpose of using the vertex $u$ in your definition? I think you can define things better by dropping the $u$ and calling $C$ as a maximal connected component. This would make sure that there is no vertex outside of $C$ which can be considered connected to $C$. (I assume that you mean strongly connected when you say connected). $\endgroup$ – mayank Apr 22 '13 at 13:28
  • $\begingroup$ If $C=(V_C,E_C)$ is a connected component then there is no edge $yz$ with $y\in V_C$ and $z\in V_G\setminus V_C$. I'm afraid the set of vertices for which this property is held is the empty set. $\endgroup$ – fidbc Apr 22 '13 at 14:14
  • $\begingroup$ @fidbc, which property are you referring to? No one said such edge $(y,z)$ should exist. I have improved the question for clarity. $\endgroup$ – liuyu Apr 22 '13 at 14:36
  • 1
    $\begingroup$ Since a component defines a cut, I'd say "cut-incident". But I don't know that this is standard terminology. $\endgroup$ – Raphael Apr 23 '13 at 11:35
  • 1
    $\begingroup$ alternatively, you can say that the out-neighbourhood of $x$ is not entirely in the component (is not a subset of $V_C$) $\endgroup$ – Ran G. Apr 25 '13 at 4:37

Your Answer

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

Browse other questions tagged or ask your own question.