Publications
Sort:
Open Access Research Article Issue
A related problem on s-Hamiltonian line graphs
AIMS Mathematics 2022, 7(10): 19553-19561
Published: 15 October 2022
Abstract PDF (239.5 KB) Collect
Downloads:2

A graph G is said to be claw-free if G does not contain K 1 , 3 as an induced subgraph. For an integer s 0, G is s-Hamiltonian if for any vertex subset S V ( G ) with | S | s, G S is Hamiltonian. Lai et al. in [On s-Hamiltonian line graphs of claw-free graphs, Discrete Math., 342 (2019)] proved that for a connected claw-free graph G and any integer s 2, its line graph L ( G ) is s-Hamiltonian if and only if L ( G ) is ( s + 2 )-connected.

Motivated by above result, we in this paper propose the following conjecture. Let G be a claw-free connected graph such that L ( G ) is 3-connected and let s 1 be an integer. If one of the following holds:

( i) s { 1 , 2 , 3 , 4 } and L ( G ) is essentially ( s + 3 )-connected,

( i i) s 5 and L ( G ) is essentially ( s + 2 )-connected,

then for any subset S V ( L ( G ) ) with | S | s, | D 1 ( L ( G ) S ) | s 2 and L ( G ) S D 1 ( L ( G ) S ) is Hamiltonian. Here, D 1 ( L ( G ) S ) denotes the set of vertices of degree at most 1 in L ( G ) S. Furthermore, we in this paper deal with the cases s { 1 , 2 , 3 , 4 } and L ( G ) is essentially ( s + 3 )-connected about this conjecture.

Total 1