Minimally tough chordal graphs with toughness at most 1/2

DOI10.1016/J.DISC.2023.113491MaRDI QIDQ6409454zbMATH OpenFDO

Authors Gyula Y. Katona, Humara Khan

Publication date 1 September 2022

Full work available at URL https://doi.org/10.1016/J.DISC.2023.113491

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $t$ be a positive real number. A graph is called emph{$t$-tough} if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. A graph is emph{chordal} if it does not contain an induced cycle of length at least $4$. We characterize the minimally $t$-tough, chordal graphs for all $tle1/2$. As a corollary, a characterization of minimally $t$-tough, interval graphs is obtained for $tle1/2$.

Recommendations

• Minimal toughness in special graph classes
• Properties of minimally \(t\)-tough graphs
• The structure of minimally t-tough, 2K₂-free graphs
• Various results on the toughness of graphs

Cited in

(3)

• Minimal toughness in special graph classes
• Constructions of minimally t-tough regular graphs
• Characterization of minimally \(t\)-tough, \(2 K_2\)-free graphs for \(1 < t \leq 2\)

This page was built for publication: Minimally tough chordal graphs with toughness at most $1/2$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409454)