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.
Citation: Xia Liu. A related problem on $ s $-Hamiltonian line graphs[J]. AIMS Mathematics, 2022, 7(10): 19553-19561. doi: 10.3934/math.20221073
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.
| [1] | J. A. Bondy, U. S. R. Murty, Graph theory, Springer, 2008. http://dx.doi.org/10.1007/978-1-84628-970-5 |
| [2] |
H. J. Broersma, H. J. Veldman, 3-connected line graphs of triangular graphs are pan-connected and 1-Hamiltonian, J. Graph Theor., 11 (1987), 399–407. https://doi.org/10.1002/jgt.3190110314 doi: 10.1002/jgt.3190110314
|
| [3] |
P. A. Catlin, A reduction method to find spanning eulerian subgraphs, J. Graph Theor., 12 (1988), 29–44. https://doi.org/10.1002/jgt.3190120105 doi: 10.1002/jgt.3190120105
|
| [4] | P. A. Catlin, Supereulerian graphs, collapsible graphs, and four-cycles, Congressus Numerantium, 58 (1988), 233–246. |
| [5] |
P. A. Catlin, Z. Y. Han, H. J. Lai, Graphs without spanning closed trals, Discrete Math., 160 (1996), 81–91. https://doi.org/10.1016/S0012-365X(95)00149-Q doi: 10.1016/S0012-365X(95)00149-Q
|
| [6] |
P. A. Catlin, H. J. Lai, Y. Shao, Edge-connectivity and edge-disjoint spanning trees, Discrete Math., 309 (2009), 1033–1040. https://doi.org/10.1016/j.disc.2007.11.056 doi: 10.1016/j.disc.2007.11.056
|
| [7] |
Z. H. Chen, H. J. Lai, W. Shiu, D. Li, An $s$-Hamiltonian line graph problem, Graph. Combinator., 23 (2007), 241–248. https://doi.org/10.1007/s00373-007-0727-y doi: 10.1007/s00373-007-0727-y
|
| [8] |
F. Harary, C. S. J. A. Nash-Williams, On eulerian and Hamiltonian graphs and line graphs, Can. Math. Bull., 8 (1965), 701–710. https://doi.org/10.4153/CMB-1965-051-3 doi: 10.4153/CMB-1965-051-3
|
| [9] |
H. J. Lai, Y. Shao, On $s$-Hamiltonian line graphs, J. Graph Theor., 74 (2013), 344–358. https://doi.org/10.1002/jgt.21713 doi: 10.1002/jgt.21713
|
| [10] |
H. J. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Comb. Theory B, 96 (2006), 571–576. https://doi.org/10.1016/j.jctb.2005.11.002 doi: 10.1016/j.jctb.2005.11.002
|
| [11] |
H. J. Lai, M. Zhan, T. Zhang, J. Zhou, On $s$-Hamiltonian line graphs of claw-free graphs, Discrete Math., 342 (2019), 3006–3016. https://doi.org/10.1016/j.disc.2019.06.006 doi: 10.1016/j.disc.2019.06.006
|
| [12] | Y. Shao, Claw-free graphs and line graphs, Ph.D. Dissertation, West Virginia University, 2005. |
Figures(1)
Xia Liu. A related problem on $ s $-Hamiltonian line graphs[J]. AIMS Mathematics, 2022, 7(10): 19553-19561. doi: 10.3934/math.20221073
DownLoad: