Calculate the toughness of a graph

savecancel

Let $G$ be a graph. Toughness is defined as $$t(G)=\min _S \frac{|S|}{c(G-S)}$$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment.

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
            if is_vertex_cut(G, j):
                # Create a copy of the graph
                H = G.copy()
                # Remove the nodes from the given set
                H.remove_nodes_from(j)
                # Calculate the number of connected components in (G-j)
                num_connected_components = nx.number_connected_components(H)
                toughness_value = r / num_connected_components
                # Update the toughness value
                min_toughness = min(min_toughness, toughness_value)

    # Return the minimum toughness value
    return min_toughness

# Test code
G = nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Then it gives us the following output:

toughness: 1.0

(run 166.5s)