✦ LIBER ✦

On hamiltonian-connected graphs

✍ Scribed by Ronald J. Gould; Xingxing Yu

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 735 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180808

No coin nor oath required. For personal study only.

✦ Synopsis

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. That is, for S ⊂ V(G), let deg S = |~x≅S~ N(x)|, where N(x) = {v|xv ≅ E(G)} is the neighborhood of x. In particular we show: In a 3‐connected graph G, if deg S~1~ + deg S~2~ ≧ |V(G)| + 1 for each pair of distinct 2‐sets of vertices S~1~, S~2~ ⊂ V(G), then G is hamiltonian‐connected.

Several corollaries and related results are also discussed.

📜 SIMILAR VOLUMES

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

Hamilton-Connected Cayley Graphs on Hami

Hamilton-Connected Cayley Graphs on Hamiltonian Groups

✍ Brian Alspach; Yusheng Qin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

It is proven that every connected Cayley graph X , of valency at least three, on a Hamiltonian group is either Hamilton laceable when X is bipartite, or Hamilton connected when X is not bipartite.

On hamiltonian line graphs and connectiv

On hamiltonian line graphs and connectivity

✍ Siming Zhan 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 444 KB

A well-known conjecture of Thomassen says that every 4-connected line graph is hamiltonian. In this paper we prove that every 7-connected line graph is hamiltonian-connected. For line graph, C. Thomassen [l] made the following conjecture. Conjecture. Every 4-connected line graph is hamiltonian.

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,

Five-Connected Toroidal Graphs Are Hamil

Five-Connected Toroidal Graphs Are Hamiltonian

✍ Robin Thomas; Xingxing Yu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 518 KB

We prove that every edge in a 5-connected graph embedded in the torus is contained in a Hamilton cycle. Our proof is constructive and implies a polynomial time algorithm for finding a Hamilton cycle. ## 1997 Academic Press On the other hand, for 4-connected graphs embedded in the torus, certain ed

All 4-connected Line Graphs of Claw Free

All 4-connected Line Graphs of Claw Free Graphs Are Hamiltonian Connected

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Thomassen conjectured that every 4-connected line graph is hamiltonian. Here we shall see that 4-connected line graphs of claw free graphs are hamiltonian connected.