2
$\begingroup$

Suppose a non-directed graph G with vertices V and paths P. What is the name for the vertex sets to make break the graph by removal of some vertices?

$\endgroup$
5
  • 1
    $\begingroup$ Are you talking about cut sets? $\endgroup$
    – JMoravitz
    Jan 4, 2016 at 20:28
  • 2
    $\begingroup$ Wait, do you want to have zero edges after removing the vertices? Or do you just want it to be disconnected? If it is the first option what you want is a dominating set $\endgroup$
    – Asinomás
    Jan 4, 2016 at 20:32
  • $\begingroup$ @JMoravitz if this cut set is defined only by the removal of edges, not vertices, no -- I am trying to find a term to describe the removal of vertices in which case relevant associated edges will dissappear: this is partially also edge removal but the focus is on removal of vertices instead of edges. Is this still called "cut set" in graph theory? $\endgroup$
    – hhh
    Jan 4, 2016 at 20:32
  • 1
    $\begingroup$ In my experience, they can be used for either "cut vertex sets" or "cut edge sets". Another name that it sometimes goes by is vertex separator. In general, if a graph is $k$-connected there does not exist $k-1$ vertices that you can delete which disconnects the graph. $\endgroup$
    – JMoravitz
    Jan 4, 2016 at 20:36
  • 1
    $\begingroup$ In infinite graph theory Dunwoody and Krön (to the best of my knowledge Dunwoody was first) called such things edge and vertex cuts. However for them (any others) an edge/vertex cut is a set of vertices with finite edge/vertex boundary (that is the set of edges/vertices which are connected with exactly one vertex of the edge/vertex cut). They have developed a beautiful theory (see the paper "Vertex cuts" by Dunwoody, Krön and also the book "Groups acting on Graphs" by Dicks, Dunwoody) which also applies to finite graphs. $\endgroup$
    – M.U.
    Jan 4, 2016 at 20:37

1 Answer 1

Reset to default
2
$\begingroup$

I list below the relevant things in Mathematics. In comparison, the computing perspectives and visualisation more here.

Theorems and Lemmas

enter image description here

  • Menger's theorem has vertex-connectivity version and edge-connectivity version

Examples

Dominating set suggested in the comment by dREaM, from dominating sets to set coverings in L-reductions here, Wikipedia about dominating set example below.

enter image description here

Cut set and vertex separator suggested in the comment by JMoravitz here and here, respectively. The examples are from the vertex separator Wikipedia article.

enter image description here

Vertex cuts and edge cuts suggested in the comment by M.U. related to infinite graph theory by Dunwoody and Krön, more in the paper "Vertex Cuts" by Dunwoody, Krön, also possible to apply to finite graphs according to M.U.

Graph separators, graph bifurcators, graph boundaries -- loosely speaking result into two separate subgraphs after removal of some vertices or some edges. (On page 12 of Graph Separators, with Applications by Arnold L. Rosenberg, et all).

References

$\endgroup$

You must log in to answer this question.

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