Panconnectivity of locally connected claw-free graphs
type: Item
instance of: scholarly article
title: Panconnectivity of locally connected claw-free graphs
zbMATH Open document ID: 0934.05078
DOI: 10.1016/S0012-365X(99)00010-2
author: Yu Sheng
author: Feng Tian
author: Bing Wei
published in: Discrete Mathematics
publication date: 2000-04-09T00:00:00Z
review text: A graph \(G\) is claw-free if \(G\) does not contain an induced subgraph isomorphic to \(K_{1,3}\). A graph \(G\) is locally connected if, for every vertex \(v\) of \(G\), the subgraph of \(G\) induced by \(N(v)\) is connected. The main result is as follows. Let \(G\) be a connected, locally connected, claw-free graph and let \(x, y\) be two vertices of \(G\). If \(T \cap \{ x, y \} = \varnothing\) for every 2-cut \(T\) of \(G\), then the graph \(G\) contains \((x,y)\)-paths of all possible lengths \(h\): \(d(x,y) \leq h \leq |V(G)|- 1\), where \(d(x,y)\) is the distance between the vertices \(x\) and \(y\). This result implies a conjecture by \textit{H. J. Broersma} and \textit{H. J. Veldman} [J. Graph Theory 11, No. 3, 399-407 (1987; Zbl 0656.05045)] that every 3-connected, locally connected, claw-free graph of order at least four contains a Hamilton circuit.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1334490
zbMATH Keywords: claw-free graph
zbMATH Keywords: \(K_{1,3}\)-free graph
zbMATH Keywords: Hamilton cycle
zbMATH Keywords: panconnectivity
zbMATH Keywords: locally connected claw-free graph
MaRDI profile type: Publication
cites work: Q4894622
cites work: Q3097395
cites work: 3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian
cites work: A note on locally connected and Hamiltonian-connected graphs
cites work: Q3958496
cites work: Connected, locally 2-connected,K1,3-free graphs are panconnected
cites work: Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
cites work: Cycles of given length in some \(K_{1,3}\)-free graphs
full work available at URL: s0012-365x(99)00010-2
OpenAlex ID: W2024359856
Recommended article: Q4887680
Recommended article: Q4940082
Recommended article: Pancyclicity in claw-free graphs
Recommended article: On pancyclic claw-free graphs
Recommended article: Q4253615
Recommended article: Q4030547
Recommended article: Quasilocally Connected, Almost Locally Connected Or Triangularly Connected Claw-Free Graphs
Recommended article: Q4294636
Recommended article: Q5109074
Recommended article: Vertex pancyclism in claw-free graphs
description: scientific article; zbMATH DE number 1334490