کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649219 1342446 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamilton connectedness and the partially square graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hamilton connectedness and the partially square graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 12, 28 June 2006, Pages 1097–1104
نویسندگان
, ,