Graph Toughness

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]


2 Responses to Graph Toughness

  1. sri says:

    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.” 🙂

  2. sanket says:

    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.

%d bloggers like this: