Name
Abstract | ||
|---|---|---|
The square of a path (cycle) is the graph obtained by joining every pair of vertices of distance two in the path (cycle). Let G be a graph on n vertices with minimum degree δ( G ). Posá conjectured that if δ( G ) ≥ 2 3 n , then G contains the square of a hamiltonian cycle. This is also a special case-of a conjecture of Seymour. In this paper, we prove that for any ϵ > 0, there exists a number m , depending only on ϵ, such that if δ( G ) ≥ ( 2 3 + ϵ) n + m , then G contains the square of a hamitonian path between any two edges, which implies the squares of a hamiltonian cycle. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1006/jctb.1995.1005 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
hamiltonian cycle | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hamiltonian path,Cycle graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
63 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
18 | 2.85 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |
| H. A. Kierstead | 2 | 700 | 78.87 |