MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
2

I have an undirected, unweighted graph representing a network. I have a starting node and an end one. My 'network' is reliable if there is no node such that without that node s and t are not reachable i.e. no node is necessary and all nodes have at least one redundant path.

how can I formally verify this? thank you

flag
What do you mean by "formally verify"? What do you mean that "all nodes have at least one redundant path"? – Igor Rivin Sep 9 at 18:22
As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected. – Andrew D. King Sep 10 at 20:25

1 Answer

3

If you mean that the network remains connected upon removing any one node, the magic words are "2-vertex-connected graph", or "biconnected graph". An algorithm for determining biconnectivity is described here, though I am sure there are plenty of other places.

link|flag
Btw, the OP has stated (without proof) a special case of Menger's theorem. – Felix Goldberg Sep 9 at 20:55

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.