Constructions of minimally t-tough regular graphs

2024/12/17 by Kun Cheng, Cheng, Kun, Chengli Li +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2412.12659

openalex publication_date 2024/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A non-complete graph G is said to be t-tough if for every vertex cut S of G, the ratio of |S| to the number of components of G-S is at least t. The toughness τ(G) of the graph G is the maximum value of t such that G is t-tough. A graph G is said to be minimally t-tough if τ(G)=t and τ(G-e)

Cited by

• On the existence of minimally tough graphs having large minimum degrees

Related

• The minimum degree of minimally t-tough graphs
• Toughness and existence of 2-factors
• Strengthening some complexity results on toughness of graphs
• On minimally tough chordal graphs
• On the minimum degree of minimally t -tough, claw-free graphs