首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Properties of minimally t-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 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 δ(G)=2. We show that in every minimally 1-tough graph δ(G)n3+1. We also prove that every minimally 1-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number t any graph can be embedded as an induced subgraph into a minimally t-tough graph.
Keywords:Toughness  Claw-free graph  Embedded subgraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号