A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path (Q2181227)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path |
scientific article |
Statements
A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path (English)
0 references
18 May 2020
0 references
Given a graph \(G\) and a positive integer \(k\), define \(\sigma_k(G)\) to be the minimum sum of the degrees of \(k\) mutually non-adjacent vertices of \(G\). This paper builds on previous work of \textit{B. Momège} [ibid. 247, 37--42 (2018; Zbl 1394.05063)]. Given an integer \(t\ge 5\), it is proved that if \(\sigma_2 (G) > \frac{t-3}{t-2}n\), then \(G\) either has a Hamiltonian path, or else an induced subgraph \(K_{1,t}\). Furthermore, graphs which have \(\sigma_2 (G) =\frac{t-3}{t-2} n\), but with no Hamiltonian path and no induced \(K_{1,t}\) are characterized.
0 references
Hamiltonian path
0 references
induced subgraph
0 references
Ore condition
0 references
0 references