Properties of minimally -tough graphs |
| |
Authors: | Gyula Y Katona Dániel Soltész Kitti Varga |
| |
Institution: | 1. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary;2. MTA-ELTE Numerical Analysis and Large Networks Research Group, Hungary |
| |
Abstract: | A graph is minimally -tough if the toughness of is and the deletion of any edge from decreases the toughness. Kriesell conjectured that for every minimally -tough graph the minimum degree . We show that in every minimally -tough graph . We also prove that every minimally -tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number any graph can be embedded as an induced subgraph into a minimally -tough graph. |
| |
Keywords: | Toughness Claw-free graph Embedded subgraph |
本文献已被 ScienceDirect 等数据库收录! |