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


Bipartite density of triangle-free subcubic graphs
Authors:Xuding Zhu
Institution:Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan National Center for Theoretical Sciences, Taiwan
Abstract:A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is defined as b(G)=max{|E(B)|/|E(G)|:B is a bipartite subgraph of G}. It was conjectured by Bondy and Locke that if G is a triangle-free subcubic graph, then View the MathML source and equality holds only if G is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result.
Keywords:Triangle-free  Subcubic  Bipartite density  Max-cut
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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