On s-hamiltonian line graphs of claw-free graphs
| Autor: | Hong-Jian Lai, Mingquan Zhan, Taoye Zhang, Ju Zhou |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science law.invention Combinatorics 010201 computation theory & mathematics law Line graph 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Mathematics::Symplectic Geometry Mathematics |
| Zdroj: | Discrete Mathematics. 342:3006-3016 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2019.06.006 |
| Popis: | For an integer s ≥ 0 , a graph G is s -hamiltonian if for any vertex subset S ⊆ V ( G ) with | S | ≤ s , G − S is hamiltonian, and G is s -hamiltonian connected if for any vertex subset S ⊆ V ( G ) with | S | ≤ s , G − S is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Kuczel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjacek and Vrana, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of s -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for s ≥ 2 , a line graph L ( G ) is s -hamiltonian if and only if L ( G ) is ( s + 2 ) -connected. In this paper we prove the following. (i) For an integer s ≥ 2 , the line graph L ( G ) of a claw-free graph G is s -hamiltonian if and only if L ( G ) is ( s + 2 ) -connected. (ii) The line graph L ( G ) of a claw-free graph G is 1-hamiltonian connected if and only if L ( G ) is 4-connected. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect