Toughness of a graph

206 Views Asked by At

I'm given an incomplete definition of the toughness of a graph $t(G)$:

$$t(G) = \min_{S \subseteq V(G)} \frac{|S|}{c(G|S)}$$

with $V(G)$ defined vertices of $G$, $S$ as any subset of $V(G)$, and $c(G|S)$ as the number of components of $G$ after deletion of $S$.

Question: is this a fraction or integer? If integer, is it the floor or ceiling?

2

There are 2 best solutions below

0
On BEST ANSWER

It is a rational number. Your definition appears to be fine. For instance, paths are $1/2$-tough because by removing one vertex you can create two connected components (and you can't get a smaller ratio).

See this link

0
On

After researching, it looks like it's the floor. That is, if $G$ is $t$ tough, then it has to be $t-1$ tough, $t-2$ tough...etc. Just silly semantics.