How tough is this graph?

409 Views Asked by At

In graph theory, toughness is a measure of the connectivity of a graph. A graph $G$ is said to be $t$-tough for a given real number $t$ if, for every integer $k > 1, G$ cannot be split into $k$ different connected components by the removal of fewer than $tk$ vertices. For instance, a graph is $1$-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum $t$ for which it is $t$-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.

I do know that this graph does not have infinite toughness because it's not complete and it's finite. Here each intersection is assumed to be a node! I could obviously not put all the nodes in. But you can see how the inner cycle all has degree $4$ and the corner nodes have degree $16$. I'm confused about the concept and how to calculate it. If someone could provide a good resource or explanation of the concept of toughness that would be awesome.

enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

The graph is $1$-tough but not $2$-tough.

First of all, we know that the graph is at most $2$-tough because there are vertices of degree $4$. If you delete all $4$ neighbors of such a vertex, you leave the graph in $2$ components; therefore the graph cannot be $3$-tough (in a $3$-tough graph, we would need to delete at least $6$ vertices to leave the graph in $2$ components). In general, a graph with minimum degree $\delta$ can be at most $\frac{\delta}{2}$-tough (unless it is the complete graph $K_{\delta+1}$).

To show the sharper bound - that the graph is not $2$-tough, either - we need to do a bit more work. In the diagram on the left, there are $8$ vertices (marked in red) whose deletion results in $5$ components: $4$ isolated vertices, and the rest of the graph. In a $2$-tough graph, this would be impossible, since at least $10$ vertices would need to be deleted to create $5$ components.

toughness illustrations

The graph is $1$-tough because it is Hamiltonian: one Hamiltonian cycle is illustrated in the diagram on the right. In general, all Hamiltonian graphs are $1$-tough. This is true because the $n$-cycle $C_n$ is $1$-tough: if we delete $k$ vertices from around the cycle, the intervals between those vertices are connected, giving us $k$ components (unless some intervals are empty, in which case the number of components is even fewer). A Hamiltonian graph is a cycle with some extra edges, and adding edges cannot reduce the toughness.

(This result is often used as a simple way to demonstrate that a graph is not Hamiltonian: by showing that it is not $1$-tough. But this doesn't always work, since there are graphs that are $1$-tough but not Hamiltonian.)