Name
Title | ||
|---|---|---|
A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path |
Abstract | ||
|---|---|---|
We say a graph G has a Hamiltonian path if it has a path containing all vertices of G. For a graph G, let σ2(G) denote the minimum degree sum of two nonadjacent vertices of G; restrictions on σ2(G) are known as Ore-type conditions. Given an integer t≥5, we prove that if a connected graph G on n vertices satisfies σ2(G)>t−3t−2n, then G has either a Hamiltonian path or an induced subgraph isomorphic to K1,t. Moreover, we characterize all n-vertex graphs G where σ2(G)=t−3t−2n and G has neither a Hamiltonian path nor an induced subgraph isomorphic to K1,t. This is an analogue of a recent result by Momège (2018), who investigated the case when t=4. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2019.12.008 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Hamiltonian path,Induced subgraph,Ore condition | Journal | 279 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilkyoo Choi | 1 | 26 | 12.04 |
| Jin-ha Kim | 2 | 329 | 18.78 |