
All graphs considered in this paper are simple and undirected. For a given graph \(G= (V,E)\) we denote by \(\delta(G)\) the minimum degree of \(G\). A \(k\)-chord of a cycle \(C\) is an edge joining two vertices of distance \(k\) on \(C\). The \(k\)th power of \(C\) is the graph obtained by joining every pair of vertices with distance at most \(k\) on \(C\). \textit{P. Seymour} [Problem section, in: Combinatorics, Proc. British Combinatorial Conference 1973, T. P. McDonough and V. C. Mavron eds., Lond. Math. Soc. Lect. Notes Ser. 13, 201-202 (1974)] conjectured that every graph \(G\) with minimum degree \(\delta(G)\geq (k/k+ 1)n\) contains the \(k\)th power of a Hamiltonian cycle. The special case \(k= 2\) of this conjecture was conjectured earlier by Pòsa: Conjecture. Let \(G\) be a graph on \(n\) vertices. If \(\delta(G)\geq {2\over 3}n\), then \(G\) contains the square of a Hamiltonian cycle. Here we use the word ``square'' instead of ``2nd power''. If true this conjecture would be best possible as is seen by considering the complete 3-partite graph on \(3m+2\) vertices with sizes \(m, m+1\) and \(m+1\) of the partite sets. In this paper, the authors prove that if \(\delta(G)\geq {5\over 7} n\) then \(G\) contains the square of a Hamiltonian cycle.
Eulerian and Hamiltonian graphs, Hamiltonian cycle, cycle, square, distance, Paths and cycles
Eulerian and Hamiltonian graphs, Hamiltonian cycle, cycle, square, distance, Paths and cycles
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 24 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
