On sufficient conditions for Hamiltonicity of graphs, and beyond

期刊论文
发表日期：

2024年2月23日

查看全文

Hechao Liu,
Lihua You,
Yufei Huang,
Zenan Du

摘要

Identifying certain conditions that ensure the Hamiltonicity of graphs is highly important and valuable due to the fact that determining whether a graph is Hamiltonian is an NP-complete problem.For a graph G with vertex set V(G) and edge set E(G), the first Zagreb index ( $M_{1}$ $M_{1}$ ) and second Zagreb index ( $M_{2}$ $M_{2}$ ) are defined as $M_{1}(G)=\sum \limits _{v_{i}v_{j}\in E(G)}(d_{G}(v_{i})+d_{G}(v_{j}))$ $M_{1} (G) = \sum_{v_{i} v_{j} \in E (G)} (d_{G} (v_{i}) + d_{G} (v_{j}))$ and $M_{2}(G)=\sum \limits _{v_{i}v_{j}\in E(G)}d_{G}(v_{i})d_{G}(v_{j})$ $M_{2} (G) = \sum_{v_{i} v_{j} \in E (G)} d_{G} (v_{i}) d_{G} (v_{j})$ , where $d_{G}(v_{i})$ $d_{G} (v_{i})$ denotes the degree of vertex $v_{i}\in V(G)$ $v_{i} \in V (G)$ . The difference of Zagreb indices ( $\Delta M$ $Δ M$ ) of G is defined as $\Delta M(G)=M_{2}(G)-M_{1}(G)$ $Δ M (G) = M_{2} (G) - M_{1} (G)$ .In this paper, we try to look for the relationship between structural graph theory and chemical graph theory. We obtain some sufficient conditions, with regards to $\Delta M(G)$ $Δ M (G)$ , for graphs to be k-hamiltonian, traceable, k-edge-hamiltonian, k-connected, Hamilton-connected or k-path-coverable.