✦ LIBER ✦

The Square of Paths and Cycles

✍ Scribed by G.H. Fan; H.A. Kierstead

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 388 KB
Volume: 63
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1005

No coin nor oath required. For personal study only.

✦ Synopsis

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 (\delta(G)). Posa conjectured that if (\delta(G) \geqslant \frac{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 (\varepsilon>0), there exists a number (m), depending only on (\varepsilon), such that if (\delta(G) \geqslant\left(\frac{2}{3}+\varepsilon\right) n+m), then (G) contains the square of a hamitonian path between any two edges, which implies the squares of a hamiltonian cycle. 1. 1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

Closures, cycles, and paths

✍ Jochen Harant; Arnfried Kemnitz; Akira Saito; Ingo Schiermeyer 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract In 1960 Ore proved the following theorem: Let __G__ be a graph of order __n__. If __d__(__u__) + __d__(__v__)≥__n__ for every pair of nonadjacent vertices __u__ and __v__, then __G__ is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have

Paths extendable to cycles

✍ T. D. Parsons 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Let __k__ be a positive integer, and __S__ a nonempty set of positive integers. Suppose that __G__ is a connected graph containing a path of length __k__, and that each path __P__ of length __k__ in __G__ is contained in some cycle __C__(__P__) of length s ∈ __S__. We prove that every p

Existence of Δλ-cycles and Δλ-paths

✍ H. J. Broersma 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 398 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

Hamilton Cycles and Paths in Fullerenes.

✍ Dragan Marusic 📂 Article 📅 2007 🏛 John Wiley and Sons ⚖ 11 KB

On relative length of longest paths and

On relative length of longest paths and cycles

✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6