Back to Search
Start Over
On sufficient conditions for Hamiltonicity of graphs, and beyond.
- Source :
- Journal of Combinatorial Optimization; Mar2024, Vol. 47 Issue 2, p1-12, 12p
- Publication Year :
- 2024
-
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 ) and second Zagreb index ( M 2 ) are defined as M 1 (G) = ∑ v i v j ∈ E (G) (d G (v i) + d G (v j)) and M 2 (G) = ∑ v i v j ∈ E (G) d G (v i) d G (v j) , where d G (v i) denotes the degree of vertex v i ∈ V (G) . The difference of Zagreb indices ( Δ M ) of G is defined as Δ 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 Δ M (G) , for graphs to be k-hamiltonian, traceable, k-edge-hamiltonian, k-connected, Hamilton-connected or k-path-coverable. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13826905
- Volume :
- 47
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Journal of Combinatorial Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 175687754
- Full Text :
- https://doi.org/10.1007/s10878-024-01110-4