Article ID Journal Published Year Pages File Type
4649219 Discrete Mathematics 2006 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,