Name of a particular property of a graph

24 Views Asked by At

Please forgive me for not having the best grasp on graph theory terminology. I am doing my best.

I have a large connected subgraph of a large graph where I want to find, what I am terming the "weak points," of the graph.

A "Weak point" exists, in my conception, when given a vertex, there exists at least one single edge among the vertex's edges that can be deleted to create two independent distinct subgraphs.

Does this character of a vertex have a name? I can imagine if one must delete two edges to create two independent subgrpahs this vertex would be a "stronger" vertex.

Thanks

1

There are 1 best solutions below

1
On BEST ANSWER

There are many terms that almost describe what you are asking for.

Firstly, we have the notion of a vertex cut, which is a set of vertices $S \subseteq V$ whose removal from the graph along with any incident edges disconnects the graph (or more generally increases the number of connected components).

A single vertex whose removal will disconnect the graph is clearly a vertex cut of size 1 and is called an articulation vertex.

The above aren't exactly what you want, since you are not looking to remove a node with all incident edges.

The same idea can be applied to edges, however, where we define an edge cut as a set of edges S $\subseteq E$, that if removed will disconnect the graph.

Once again, a single edge whose removal achieves this is an edge cut of size 1 and also has a special name. It's called a bridge.

What you are describing as a "weak point", sounds like a node that is incident to a bridge, or equivalently a bridge endpoint.