𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonicity in 2-connected graphs with claws

✍ Scribed by Hao Li; Mei Lu; Zhiren Sun

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
562 KB
Volume
183
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Matthews and Sumner have proved in [12] that if G is a 2-connected claw-free graph of order n such that 6>~(n-2)/3, then G is hamiltonian. Li has shown that the bound for the minimum degree 6 can be reduced to n/4 under the additional condition that G is not in /7, where /7 is a class of graphs defined in [7]. On the other hand, we say that a graph G is almost claw-free if the centres of induced claws are independent and their neighbourhoods are 2-dominated. Broersma, Ryjfirek and Schiermeyer have proved that if G is 2-connected almost claw-free graph of order n such that 6 >~(n -2)/3, then G is hamiltonian. We generalize these results by considering the graphs whose claw centres are independent. If G is a 2-connected graph of order n and minimum degree 6 such that n ~< 46 -3 and if the set of claw centres of G is independent, then we show that either G is hamiltonian or G C F, where F is a class of graphs defined in the paper. The bound n<~46 -3 is sharp.

📜 SIMILAR VOLUMES

Hamiltonicity of 2-connected claw-center
Hamiltonicity of 2-connected claw-center independent graphs
✍ Hao Li; Mei Lu; Feng Tian; Bing Wei 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 679 KB

In this paper, we give the following result: Let G be a 2-connected graph of order PZ> 13 and nd2az -3, where 02 = min{d(u) + d(u): uz'.$E(G)}. If the set of claw-centers of G is independent, then either G is hamiltonian or G belongs to three classes of exceptional graphs. The bound n <202 -3 is sha

9-Connected Claw-Free Graphs Are Hamilto
9-Connected Claw-Free Graphs Are Hamilton-Connected
✍ Stephan Brandt 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 130 KB

A graph is Hamilton-connected if any pair of vertices is joined by a hamiltonian path. In this note it is shown that 9-connected graphs which contain no induced claw K 1, 3 are Hamilton-connected, by reformulating and localizing a closure concept due to Ryja c ek, which turns claw-free graphs into l

Hamiltonicity of regular 2-connected gra
Hamiltonicity of regular 2-connected graphs
✍ Broersma, H. J.; van den Heuvel, J.; Jackson, B.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 832 KB

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n 5 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to q k if G is 3-connected and k 2 63. We improve both results by showing that G is hamiltonian if n 5 gk -7 and G does not belong to a res

Hamilton connectivity of line graphs and
Hamilton connectivity of line graphs and claw-free graphs
✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co

Every 3-connected, locally connected, cl
Every 3-connected, locally connected, claw-free graph is Hamilton-connected
✍ Asratian, A. S. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 639 KB

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of orderp 2 4, containing no induced subgraph isomorphic to K1,31 is Hamilton-connected if and only if G is 3connected.

Hourglasses and Hamilton cycles in 4-con
Hourglasses and Hamilton cycles in 4-connected claw-free graphs
✍ Tomáš Kaiser; MingChu Li; Zdeněk Ryjáček; Liming Xiong 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

## Abstract We show that if __G__ is a 4‐connected claw‐free graph in which every induced hourglass subgraph __S__ contains two non‐adjacent vertices with a common neighbor outside __S__, then __G__ is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamilton