✦ LIBER ✦

On graphs with hamiltonian squares

✍ Scribed by P. Underground

Publisher: Elsevier Science
Year: 1978
Tongue: English
Weight: 111 KB
Volume: 21
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(78)90164-4

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of recognizing hamiltonian graphs is not Jriously difficult; in fack, Karp, Lawler and Tarjan [3] proved that it is NP-colnplete. Combined with Cook's theorem [l], this result suggests that the existence'= of a good characterization of nonhamiltcnian graphs is extremely unlikely. On the other hand, the problem of recognizing graphs with hamiltonian squares may seem easier, in view of Fleischner's [Z] proof of the conjecture due to Nash-iViPlia:ns and Plummer: every 'R-connected graph has a hamiltonian square. We shall point out that the two problems are, in fact, equivalent: given a graph G, we shall construct a graph H such that G is hamiltonian if ;and only if H2 is hamiltonian.

(1)

📜 SIMILAR VOLUMES

Graphs with exactly one hamiltonian circ

Graphs with exactly one hamiltonian circuit

✍ John Sheehan 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB

## Abstract Let __h(n__) be the largest integer such that there exists a graph with __n__ vertices having exactly one Hamiltonian circuit and exactly __h(n__) edges. We prove that __h(n__) = [__n__^2^/4]+1 (__n__ ≧ 4) and discuss some related problems.

On hamiltonian line graphs

✍ Lane Clark 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

On hamiltonian-connected graphs

✍ Ronald J. Gould; Xingxing Yu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 735 KB

## Abstract One of the most fundamental results concerning paths in graphs is due to Ore: In a graph __G__, if deg __x__ + deg __y__ ≧ |__V__(__G__)| + 1 for all pairs of nonadjacent vertices __x, y__ ≅ __V__(__G__), then __G__ is hamiltonian‐connected. We generalize this result using set degrees.

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian

On hamiltonian claw-free graphs

✍ E. Flandrin; J.L. Fouquet; H. Li 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 515 KB

We show that every 3-connected claw-free graphs having at most 5S-10 vertices is hamiltonian, where 6 is the minimum degree. For regular 3-connected claw-free graphs, a related result was obtained by Li and Liu (preprint), but for nonregular claw-free graphs the best-known result comes from the work

Hamiltonian graphs with neighborhood int

Hamiltonian graphs with neighborhood intersections

✍ G. Chen; R. H. Schelp 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 577 KB

## Abstract In this paper, __k__ + 1 real numbers __c__~1~, __c__~2~, ⃛, __c__~__k__+1~ are found such that the following condition is sufficient for a __k__‐connected graph of order __n__ to be hamiltonian: for each independent vertex set of __k__ + 1 vertices in __G__. magnified image where S~i~