کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649219 | 1342446 | 2006 | 8 صفحه PDF | دانلود رایگان |

Let G be a κκ-connected graph on n vertices. The partially square graph G*G* of G is obtained by adding edges uvuv whenever the vertices u,vu,v have a common neighbor x satisfying the condition NG(x)⊂NG[u]∪NG[v]NG(x)⊂NG[u]∪NG[v]. Clearly G⊆G*⊆G2G⊆G*⊆G2, where G2G2 is the square of G . In particular G*=G2G*=G2 if G is quasi-claw-free (and claw-free). In this paper we prove that a κκ-connected, (κ⩾3)(κ⩾3) graph G is either hamiltonian-connected or the independence number of G*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)<κα(G2)<κ is hamiltonian-connected.
Journal: Discrete Mathematics - Volume 306, Issue 12, 28 June 2006, Pages 1097–1104