Minimal toughness in subclasses of weakly chordal graphs

This paper initiates the study of minimally tough graphs within the class of weakly chordal graphs by providing complete classifications for several specific subclasses and offering simplified proofs for existing results.

The Gist

Imagine a graph as a city made of buildings (vertices) connected by roads (edges).

The Core Concept: "Toughness"

In this paper, the authors are studying a property called Toughness. Think of toughness as the city's structural integrity or resilience.

• The Test: Imagine a disaster strikes, and you have to remove a certain number of buildings (a "separator") to break the city into isolated islands (disconnected components).
• The Ratio: Toughness asks: How many buildings did you have to destroy to create how many islands?
  • If you destroy 1 building and the city splits into 10 islands, the city is fragile (low toughness).
  • If you have to destroy 100 buildings just to split the city into 2 islands, the city is tough (high toughness).
• The Goal: The authors are looking for cities that are Minimally Tough. These are cities that are just barely strong enough. If you remove even a single road, the city instantly becomes much more fragile. It's the "Goldilocks" zone of structural integrity: not too weak, but not over-engineered.

The Big Mystery

For a long time, mathematicians wondered: Can you build a "Minimally Tough" city that is very strong (high toughness) but has a specific, simple shape (called a "chordal" graph)?

• The Conjecture: They suspected the answer was No. They thought that if a city has this simple shape, it can't be both "minimally tough" and "very strong" at the same time.
• The Twist: The authors of this paper decided to look at a slightly larger, more complex family of cities called Weakly Chordal Graphs. They wanted to see if the rules changed here.

The Discovery: "Yes, they exist!"

The authors found that yes, you can build cities in this larger family that are both minimally tough and incredibly strong. In fact, you can make them as strong as you want!

To prove this, they didn't just guess; they acted like architects and inspectors, categorizing every possible type of city in this family to see which ones fit the "Minimally Tough" criteria. They looked at five specific types of city layouts:

1. Co-Chordal Cities (The Mirror Image): Cities where the "non-roads" form a simple pattern.
2. Net-Free Cities: Cities that don't have a specific "three-pronged" trap shape.
3. Forest Complements: Cities that are the opposite of a forest (a collection of trees).
4. P4-Free Cities: Cities that don't have a specific "four-building straight line" pattern.
5. Complete Multipartite Cities: Cities divided into distinct neighborhoods where everyone in Neighborhood A is connected to everyone in Neighborhood B, but no one in Neighborhood A is connected to anyone else in Neighborhood A.

The "Blueprints" (The Results)

The authors created a "cheat sheet" (Theorems 1.1 to 1.5) that lists exactly which city shapes work.

• The "Stars": Some minimally tough cities look like a central hub with spokes (like a starfish).
• The "Wheels": Some look like a wheel with a rim and spokes.
• The "Balanced Teams": Some are perfectly balanced groups where everyone is connected to everyone outside their group.

The Big Surprise: They found that Complete Multipartite Cities (the "Balanced Teams") can be made with arbitrarily large toughness.

• Analogy: Imagine a city divided into 1,000 tiny neighborhoods. If you remove 1 building, the city doesn't split. You have to remove a huge chunk of buildings to break it apart. The authors proved that you can design these cities so that they are minimally tough (remove one road, and they break) but still incredibly hard to destroy.

The "Universal Vertex" Rule

A key tool the authors used was the concept of a "Universal Vertex" (a building connected to every other building in the city).

• They proved a rule: If a city has a "Universal Vertex," it can only be minimally tough if the rest of the city follows a very strict, regular pattern (like a perfect ring or a set of disconnected pairs).
• This helped them quickly rule out many complex city shapes that couldn't be minimally tough.

Why Does This Matter?

1. Solving a Riddle: They settled a debate about whether strong, minimally tough graphs exist in these specific categories. They proved they do, and they gave the exact blueprints.
2. The "Degree" Conjecture: There is a famous guess (Kriesell's Conjecture) that says every minimally tough city must have at least one "weak link" (a building with very few roads connected to it). The authors proved that for all the city types they studied, this guess is true.
3. Future Maps: By mapping out these specific city types, they are paving the way to solve the bigger mystery: What do minimally tough graphs look like in general?

Summary in a Nutshell

The authors took a complex math problem about "structural strength" in networks. They acted like master architects, examining five different types of network designs. They discovered that while some designs can't be both "strong" and "minimally tough," others (specifically balanced, multi-group networks) can be incredibly strong while still being on the edge of breaking. They provided the exact blueprints for these networks, proving that the "strongest" minimally tough graphs can be as strong as we can imagine.

Technical Summary

Here is a detailed technical summary of the paper "Minimal Toughness in Subclasses of Weakly Chordal Graphs" by Gollin, Milanič, and Ogrin.

1. Problem Statement and Motivation

Core Concept: Toughness
The toughness $\tau(G)$ of a graph $G$ is a measure of its connectivity, defined as the largest real number $t$ such that for every vertex cut $S$ (where $G-S$ is disconnected), the inequality $|S| \ge t \cdot c(G-S)$ holds, where $c(G-S)$ is the number of connected components. If $G$ is complete, $\tau(G) = \infty$.

Minimal Toughness
A graph is minimally $t$-tough if $\tau(G) = t$ and removing any edge $e$ results in $\tau(G-e) < t$. The study of such graphs is motivated by Chvátal's conjecture, which posits that there exists a threshold $t_0$ such that every $t_0$-tough graph is Hamiltonian. This is equivalent to asking if every minimally $t_0$-tough graph is Hamiltonian.

The Open Question
A significant open problem, conjectured by Dallard et al., is whether there exists a minimally tough chordal graph with toughness $t > 1$. While it is known that no such chordal graphs exist for $1/2 < t \le 1$, the existence for$t > 1$ remains unresolved.

Research Goal
The authors extend the investigation from chordal graphs to the broader class of weakly chordal graphs (graphs with no induced cycles of length $\ge 5$ and no induced cycles of length $\ge 5$ in their complements). The primary objective is to classify minimally tough graphs within specific subclasses of weakly chordal graphs to understand the structural constraints on minimal toughness.

2. Methodology

The authors employ a combination of structural graph theory, local connectivity analysis, and combinatorial optimization techniques.

• Join Condition (The Join of Graphs): A central tool is the analysis of graphs formed by the join of two graphs ($G = G_1 \ast G_2$). They establish a necessary condition (Condition 1.6): If $G = G_1 \ast G_2$ is minimally tough and one part contains a vertex of maximum degree in $G$, the other part must be regular. This reduces the classification problem to analyzing regular graphs and specific join structures.
• Dominating Edges: The paper heavily utilizes the concept of a dominating edge (an edge $uv$ such that $N(u) \cup N(v) = V(G)$). They prove that for a minimally tough graph with a dominating edge, the local connectivity $\kappa_G(u,v)$ must satisfy $\kappa_G(u,v) < 2t + 1$. This condition is crucial for ruling out non-minimal cases.
• Local Connectivity via Matchings: To calculate local connectivity in specific structures (like the complement of chordal graphs), the authors relate the number of internally vertex-disjoint paths between two vertices to the size of a maximum matching in a derived bipartite graph (Lemma 3.2).
• Structural Decomposition:
  • For $P_4$-free graphs (cographs), they utilize the canonical decomposition theorem (Corneil et al.), which states that connected $P_4$-free graphs are joins of smaller components.
  • For co-chordal graphs, they leverage the existence of simplicial vertices in chordal graphs (Lemma 2.2) to analyze the distance between vertices in the complement.
  • They use the Helly property for closed neighborhoods to characterize net-free co-chordal graphs.

3. Key Contributions and Results

The paper provides complete classifications of non-trivially minimally tough graphs for five specific subclasses of weakly chordal graphs.

A. $P_4$-free Graphs (Cographs)

Theorem 1.1: A $P_4$-free graph is non-trivially minimally tough if and only if it is isomorphic to one of:

• $K_{2,3}$
• $K_{1,\ell}$ (Star graphs, $\ell \ge 2$)
• $T_{2\ell, \ell}$ (Complete multipartite graphs with $\ell$ parts of size 2)
• $T_{2\ell-1, \ell}$ (Complete multipartite graphs with one part of size 1 and $\ell-1$ parts of size 2)

Significance: This implies that all minimally tough $P_4$-free graphs are complete multipartite graphs.

B. Co-chordal Graphs with Co-diameter $\ge 3$

Theorem 1.3: A co-chordal graph with co-diameter at least 3 is non-trivially minimally tough if and only if it is isomorphic to one of:

• $P_4$
• $K_{2,3}$
• $K_{1,\ell}$
• $S_{k,\ell}$ (Double stars: two stars connected by an edge between centers)
• $T_{2\ell, \ell}$ or $T_{2\ell-1, \ell}$

C. Net-free Co-chordal Graphs

Theorem 1.4: The class of net-free co-chordal graphs (which includes complements of interval and strongly chordal graphs) admits the same classification as Theorem 1.3.
Note: The "net" is $K_3$ with a pendant edge on each vertex.

D. Complements of Forests

Theorem 1.5: A complement of a forest is non-trivially minimally tough if and only if it is isomorphic to:

• $P_4$
• $T_{2\ell, \ell}$
• $T_{2\ell-1, \ell}$
  Note: Unlike the general co-chordal case, star graphs ($K_{1,\ell}$) and double stars ($S_{k,\ell}$) are excluded because their complements are not forests (or result in disconnected complements).

E. Complete Multipartite Graphs

Theorem 1.2: As a corollary of the $P_4$-free result, the authors provide a complete classification of minimally tough complete multipartite graphs, confirming the list in Theorem 1.1.

F. Toughness Values

The authors derive exact toughness values for these graphs (Table 1.1). Notably, they show that minimally tough complete multipartite graphs can have arbitrarily large finite toughness. For example, the toughness of $T_{2\ell, \ell}$ is $\frac{2\ell}{2} - 1 = \ell - 1$, which grows with $\ell$. This contrasts with the open question for chordal graphs, where no minimally tough graph with $t > 1$ is known.

4. Verification of Conjectures

Generalized Kriesell's Conjecture
This conjecture states that every minimally $t$-tough graph has a vertex of degree $\lceil 2t \rceil$.

• The authors verify this conjecture for all the classes they classified ($P_4$-free, co-chordal with co-diameter $\ge 3$, net-free co-chordal, and complements of forests).
• They show that for every graph in their classification, the minimum degree $\delta(G)$ equals $\lceil 2t \rceil$.

Refinement of Dallard et al.'s Results
The authors provide simplified proofs for results regarding minimally tough graphs with a universal vertex:

• They extend the classification of such graphs for $t \le 1$ to $t \le 3/2$.
• They prove that for $t \in (1, 3/2]$, the only minimally tough graphs with a universal vertex are Wheel graphs ($W_\ell$).
• They re-prove that no minimally tough chordal graph with a universal vertex exists for $t > 1$.

5. Significance and Open Problems

Significance:

1. Existence of High Toughness: The paper definitively shows that minimally tough graphs with arbitrarily large toughness exist within the weakly chordal class (specifically in complete multipartite graphs), whereas this is an open question for chordal graphs.
2. Structural Characterization: The results provide a comprehensive structural understanding of how minimal toughness constrains graph topology in these subclasses, linking toughness directly to regularity and specific join structures.
3. Algorithmic Implications: By characterizing these classes, the paper aids in understanding the complexity landscape of recognizing minimally tough graphs, which is generally DP-complete.

Open Problems:

• General Weakly Chordal Graphs: The authors pose the problem of characterizing minimally tough graphs in the entire class of weakly chordal graphs.
• Co-chordal Graphs with Co-diameter 2: The classification remains open for co-chordal graphs where the complement has diameter 2 and contains an induced "co-net." The authors conjecture these are exactly the graphs $S_{\ell,\ell,\ell}$ (three stars connected by a triangle between centers).
• Chordal Graphs ($t > 1$): The fundamental question of whether a minimally tough chordal graph with $t > 1$ exists remains open, though the results here suggest such graphs, if they exist, must be structurally very different from the weakly chordal examples found.

In summary, this paper significantly advances the theory of graph toughness by mapping the landscape of minimally tough graphs in weakly chordal subclasses, resolving the generalized Kriesell conjecture for these classes, and demonstrating that high toughness is achievable in non-chordal weakly chordal graphs.