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


Hamilton connectedness and the partially square graphs
Authors:Ahmed Ainouche  Serge Lapiquonne
Institution:UAG—Grimaag, B.P. 7209, 97275 Schoelcher Cedex, Martinique, France
Abstract:Let G be a κ-connected graph on n vertices. The partially square graphG* of G is obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition NG(x)⊂NGu]∪NGv]. Clearly GG*G2, where G2 is the square of G. In particular G*=G2 if G is quasi-claw-free (and claw-free). In this paper we prove that a κ-connected, (κ?3) graph G is either hamiltonian-connected or the independence number of G* is at least κ. As a consequence we answer positively two open questions. The first one by Ainouche and Kouider and the second one by Wu et al. As a by-product we prove that a quasi-claw-free (and hence a claw-free) graph satisfying the condition α(G2)<κ is hamiltonian-connected.
Keywords:Hamiltonicity  Partially square graph  Degree sum  Independent sets  Neighborhood unions and intersections  Quasi-claw-free graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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