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


On clique convergent graphs
Authors:Claudson F Bornstein  Jayme L Szwarcfiter
Institution:(1) Instituto de Matemática and NCE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001 Rio de Janeiro, RJ, Brazil;(2) Present address: School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave., 15213 Pittsburgh, PA, USA
Abstract:A graphG isconvergent when there is some finite integern ge 0, such that then-th iterated clique graphK n(G) has only one vertex. The smallest suchn is theindex ofG. TheHelly defect of a convergent graph is the smallestn such thatK n(G) is clique Helly, that is, its maximal cliques satisfy the Helly property. Bandelt and Prisner proved that the Helly defect of a chordal graph is at most one and asked whether there is a graph whose Helly defect exceeds the difference of its index and diameter by more than one. In the present paper an affirmative answer to the question is given. For any arbitrary finite integern, a graph is exhibited, the Helly defect of which exceeds byn the difference of its index and diameter.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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