A related problem on s " role="presentation" style="position: relative;"> s s s -Hamiltonian line graphs

AIMS Mathematics

article

Xia Liu¹ 

[1] Department of Mathematics, Northwest Normal University;Key Laboratory of Discrete Mathematics with Applications of Ministry of Education, Center for Applied Mathematics of Fujian Province, Key Laboratory of Operations Research and Cybernetics of Fujian Universities, Fuzhou University

关键词: essentially;    $ s $-Hamiltonian;    supereulerian;    collapsible;    dominating;   

DOI  :  10.3934/math.20221073

学科分类：地球科学(综合)

来源: AIMS Press

【 摘 要 】

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\geq0 $, $ G $ is $ s $-Hamiltonian if for any vertex subset $ S\subset V(G) $ with $ |S|\leq 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\geq 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\geq1 $ be an integer. If one of the following holds:($ i $) $ s\in\{1, 2, 3, 4\} $ and $ L(G) $ is essentially $ (s+3) $-connected,($ ii $) $ s\geq5 $ and $ L(G) $ is essentially $ (s+2) $-connected,then for any subset $ S\subseteq V(L(G)) $ with $ |S|\leq s $, $ |D_{\leq1}(L(G)-S)|\leq\left \lfloor \frac{s}{2} \right \rfloor $ and $ L(G)-S-D_{\leq1}(L(G)-S) $ is Hamiltonian. Here, $ D_{\leq1}(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\in\{1, 2, 3, 4\} $ and $ L(G) $ is essentially $ (s+3) $-connected about this conjecture.

【 授权许可】

CC BY