Name
Abstract | ||
|---|---|---|
A hamiltonian square-path (-cycle) is one obtained from a hamiltonian path (cycle) 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á and Seymour conjectured that if δ ( G )⩾ 2 3 n , then G contains a hamiltonian square-cycle. We prove that if δ ( G )⩾(2 n −1)/3, then G contains a hamiltonian square-path. A consequence of this result is a theorem of Aigner and Brandt that confirms the case Δ ( H )=2 of the Bollabás–Eldridge Conjecture: if G and H are graphs on n vertices and ( Δ ( G )+1)( Δ ( H )+1)⩽ n +1, then G and H can be packed. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/jctb.1996.0039 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
hamiltonian square-paths,hamiltonian path | Discrete mathematics,Graph,Combinatorics,Hamiltonian (quantum mechanics),Vertex (geometry),Hamiltonian path,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
67 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
17 | 2.21 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |
| H. A. Kierstead | 2 | 17 | 2.21 |