On sufficient conditions for Hamiltonicity of graphs, and beyond

Hechao Liu (), Lihua You (), Yufei Huang () and Zenan Du ()
Additional contact information
Hechao Liu: Hubei Normal University
Lihua You: South China Normal University
Yufei Huang: Guangzhou Civil Aviation College
Zenan Du: South China Normal University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 2, No 10, 12 pages

Abstract: Abstract 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 ) = ∑ v i v j ∈ 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 ) = ∑ v i v j ∈ 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 ∈ 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.

Keywords: Hamiltonicity; Difference of Zagreb indices; Sufficient condition; 05C45; 05C09; 05C40 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01110-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:2:d:10.1007_s10878-024-01110-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01110-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().