Publications

On $s$-hamiltonicity of net-free line graphs.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Discrete Mathematics
Year: 2021
Abstract: The famous Thomassen Conjecture states that every 4-connected line graph is hamiltonian. It is equivalent to several seemingly stronger conjectures. Towards the Thomassen Conjecture, there has been much research on $s$-hamiltonian properties and $s$@-Hamilton@-connected properties in line graphs, where $s\ge 0$ is an integer, and a graph $G$ of order $n\ge s+3$ is $s$-hamiltonian (or $s$-Hamilton-connected, respectively) if for any $X\subseteq V(G)$ with $|X|\le s$, $G-X$ is hamiltonian (or Hamilton-connected, respectively). \par For integers $s_1,s_2,s_3>0$, denote $N_{s_1,s_2,s_3}$ as the graph obtained by identifying each vertex of a $K_3$ with an end vertex of three disjoint paths $P_{s_1+1}$, $P_{s_2+1}$, $P_{s_3+1}$ of lengths $s_1$, $s_2$ and $s_3$, respectively. In this paper, the authors prove the following results: \roster \item Let $\Cal{N}_1=\{N_{s_1,s_2,s_3}:\,s_1>0,\,s_1\ge s_2\ge s_3\ge 0\ \text{and}\,s_1+s_2+s_3\le 6\}$. Then for any $N\in\Cal{N}_1$, every $N$-free line graph $L(G)$ with $|V(L(G))|\ge s+3$ is $s$-hamiltonian if and only if $\kappa(L(G))\ge s+2$. \item Let $\Cal{N}_2=\{N_{s_1,s_2,s_3}:\,s_1>0,\,s_1\ge s_2\ge s_3\ge 0\ \text{and}\ s_1+s_2+s_3\le 4\}$. Then for any $N\in\Cal{N}_2$, every $N$-free line graph $L(G)$ with $|V(L(G))|\ge s+3$ is $s$@-Hamilton@-connected if and only if $\kappa(L(G))\ge s+3$. \endroster
Link: On $s$-hamiltonicity of net-free line graphs.