✦ LIBER ✦

Paths extendable to cycles

✍ Scribed by T. D. Parsons

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 128 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020408

No coin nor oath required. For personal study only.

✦ Synopsis

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 path of length less than k can be extended to a path of length k in G. This result answers conjectures of Entringer and Reid regarding when certain paths may be extended to cycles.

📜 SIMILAR VOLUMES

Endpoint extendable paths in tournaments

✍ Faudree, Ralph J.; Gy�rf�s, Andr�s 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

Let s(n) be the threshold for which each directed path of order smaller than s ( n ) is extendible from one of its endpoints in some tournament T,. It is shown that s(n) is asymptotic to 3n/4, with an error term at most 3 for infinitely many n. There are six tournaments with s ( n ) = n.

Hamiltonian cycles in n-extendable graph

Hamiltonian cycles in n-extendable graphs

✍ Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB

## Abstract A graph __G__ of order at least 2__n__+2 is said to be __n__‐extendable if __G__ has a perfect matching and every set of __n__ independent edges extends to a perfect matching in __G__. We prove that every pair of nonadjacent vertices __x__ and __y__ in a connected __n__‐extendable graph

Orthogonal double covers by super-extend

Orthogonal double covers by super-extendable cycles

✍ Christian Bey; Sven Hartmann; Uwe Leck; Volker Leck 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An Orthogonal Double Cover (ODC) of the complete graph __K__~__n__~ by an almost‐hamiltonian cycle is a decomposition of 2__K__~__n__~ into cycles of length __n__−1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If __n

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

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