A small quiz – do you know what toughness of a graph is? Hint: what does it mean to say a circle topology is 1-tough?

[If you don’t know it already, just guess; should be simple to guess. If you know it already, don’t answer for now. Don’t point to the wikipedia (or any other) page in any case :p]

This entry was posted on Monday, March 17th, 2008 at 5:11 am and is filed under generic, graph theory. You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.

Yeah, it is a measure of robustness or resilience. It needs another number, say ‘k’ to define it completely. A toughness of ‘t’ would mean that, for a given ‘k’, at least ‘t*k’ nodes need to be removed to fragment the graph into ‘k’ connected components. Value of k should be greater than 1. It does not make sense for k <= 1. 1-toughness would mean that, if I remove, say 3 nodes, then I should get a maximum of 3 components. 2-toughness in this case would mean 6 nodes. The toughness of a graph is the biggest value of such a ‘t’.

Toughness is also interesting because it is related to Hamiltonicity.

And regarding the citation experts, well, at times they spoil the fun.

guessing.. toughness = robustness? As in, what is the minimum number of nodes that we need to shut down in order to partition the graph?

I too get a tad irritated with citation experts.. and developed this quote for myself: “Related work is not your work.” 🙂

Yeah, it is a measure of robustness or resilience. It needs another number, say ‘k’ to define it completely. A toughness of ‘t’ would mean that, for a given ‘k’, at least ‘t*k’ nodes need to be removed to fragment the graph into ‘k’ connected components. Value of k should be greater than 1. It does not make sense for k <= 1. 1-toughness would mean that, if I remove, say 3 nodes, then I should get a maximum of 3 components. 2-toughness in this case would mean 6 nodes. The toughness of a graph is the biggest value of such a ‘t’.

Toughness is also interesting because it is related to Hamiltonicity.

And regarding the citation experts, well, at times they spoil the fun.