✦ LIBER ✦

Hamiltonian Square-Paths

✍ Scribed by Genghua Fan; H.A Kierstead

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 425 KB
Volume: 67
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0039

No coin nor oath required. For personal study only.

✦ Synopsis

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). Posa and Seymour conjectured that if $(G) 2

3 n, then G contains a hamiltonian square-cycle. We prove that if $(G) (2n&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 2(H)=2 of the Bollaba s Eldridge Conjecture: if G and H are graphs on n vertices and (2(G)+1)(2(H)+1) n+1, then G and H can be packed.

1996 Academic Press, Inc. 7 n, then G contains a hamiltonian square-cycle. Next the authors [6] showed that for every =>0, there exists m such that if n>m and article no.

📜 SIMILAR VOLUMES

Hamiltonian paths and hamiltonian connec

Hamiltonian paths and hamiltonian connectivity in graphs

✍ Bing Wei 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 388 KB

## Let G be a 2-connected graph with n vertices such that d(u)+d(u)+d(w)-IN(u)nN(u)nN(w)I an+ 1 holds for any triple of independent vertices u, v and w. Then for any distinct vertices u and u such that {u, 0) is not a cut vertex set of G, there is a hamiltonian path between u and o. In particular,

Hamiltonian path graphs

✍ Gary Chartrand; S. F. Kapoor; E. A. Nordhaus 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 389 KB

## Abstract The Hamiltonian path graph __H(G)__ of a graph __G__ is that graph having the same vertex set as __G__ and in which two vertices __u__ and __v__ are adjacent if and only if __G__ contains a Hamiltonian __u‐v__ path. A characterization of Hamiltonian graphs isomorphic to their Hamiltonia

Chromatic Roots and Hamiltonian Paths

✍ C. Thomassen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 89 KB

We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to then the graph has no hamiltonian path. This result is best possible in the sense that it becomes false if t 0 is replaced by any larger number.

Hamiltonian paths on 3-polytopes

✍ P.R Goodey 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 522 KB

Hamiltonian paths in oriented graphs

✍ Maria Overbeck-Larisch 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 217 KB

Hamiltonian paths and cycles in hypertou

Hamiltonian paths and cycles in hypertournaments

✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertour