Hamilton connectedness and the partially square graphs |
| |
Authors: | Ahmed Ainouche Serge Lapiquonne |
| |
Affiliation: | 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)⊂NG[u]∪NG[v]. Clearly G⊆G*⊆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 等数据库收录! |