Properties of minimally t-tough graphs

DOI10.1016/J.DISC.2017.08.033MaRDI QIDQ2411622zbMATH OpenOpenAlexFDO

Authors Gyula Y. Katona, Kitti Varga, Daniel Soltész

Publication date 24 October 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.02746

zbMATH Keywords

claw-free graphtoughnessembedded subgraphminimally \(t\)-tough

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Abstract: A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and the deletion of any edge from $G$ decreases the toughness. Kriesell conjectured that for every minimally $1$-tough graph the minimum degree $delta(G)=2$. We show that in every minimally $1$-tough graph $delta(G)lefracn+23$. We also prove that every minimally $1$-tough claw-free graph is a cycle. On the other hand, we show that for every $tinmathbbQ$ any graph can be embedded as an induced subgraph into a minimally $t$-tough graph.

Recommendations

• Toughness of \(K_{a,t}\)-minor-free graphs
• Properties of edge-tough graphs
• scientific article; zbMATH DE number 5522
• On the toughness of graphs
• scientific article; zbMATH DE number 165068
• Algebraic conditions for t-tough graphs
• On the Toughness of a Graph
• scientific article; zbMATH DE number 109208
• The complexity of recognizing minimally tough graphs
• Toughness and triangle-free graphs

Cites work

• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• A remark on Hamiltonian cycles
• Eine Eigenschaft der Atome endlicher Graphen
• Hamiltonian results inK1,3-free graphs
• On the complexity of recognizing tough graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(13)

• The complexity of recognizing minimally tough graphs
• The structure of minimally \(t\)-tough, \(2K_2\)-free graphs
• The toughness of a toroidal graph with connectivity 3 and girth 6 is exactly 1
• The structure of minimally 1-tough graphs with small independence number
• Minimal toughness in special graph classes
• Minimally tough chordal graphs with toughness at most $1/2$
• On minimally 1-tough (P₂ 3P₁)-free graphs
• Constructions of minimally t-tough regular graphs
• On minimally t-tough graphs with t 1
• On the minimum degree of minimally 1-tough, triangle-free graphs and minimally 3/2-tough, claw-free graphs
• On the minimum degree of minimally t-tough, claw-free graphs
• Characterization of minimally \(t\)-tough, \(2 K_2\)-free graphs for \(1 < t \leq 2\)
• Disproof of a conjecture on minimally \(t\)-tough graphs

This page was built for publication: Properties of minimally \(t\)-tough graphs

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