|
| Minimum Degrees of Minimally 1∕k-tough Graphs |
| Kai Gao,Jing Chen,Shiyu Cao |
| (School of Mathematics and Statistics, Shandong Normal University,
Jinan 250358, China) |
| DOI： |
| Abstract: |
| Let t be a non-negative real number. If a graph G has toughness
t, and deleting any edge of G decreases its toughness, then G is a minimally
t-tough graph. Katona et al. conjectured that the minimum degree of every
minimally t-tough graph is ?2t?. Although the conjecture is disproved in general, authors attempt to confirm it for some classes of graphs. In this paper,
for each positive integer k ≥2, we prove that every minimally k
1
-tough graph
whose matching number is at most 3 has a vertex of degree one. |
| Key words: minimally t-tough; toughness; matching number; minimum degree. |