Hamiltonian degree conditions for tough graphs (Q1896350)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian degree conditions for tough graphs |
scientific article |
Statements
Hamiltonian degree conditions for tough graphs (English)
0 references
27 August 1995
0 references
Let \(G\) be a graph with degree sequence \(d_1, d_2,\dots, d_n\) and \(t\) a positive integer. It is shown that if \(G\) is \(t\)-tough and for any \(i\) with \(t\leq i< n/2\) we have \(d_i\leq i\Rightarrow d_{n- i+ 1}\geq n- i\), then \(G\) is hamiltonian. This result generalizes a theorem of Chvátal for the case \(t= 1\). A similar sufficient condition is obtained for pancyclicity of graphs.
0 references
tough graphs
0 references
degree sequence
0 references
hamiltonian
0 references
pancyclicity
0 references