✦ LIBER ✦

Double coverings of 2-paths by Hamilton cycles*

✍ Scribed by Midori Kobayashi; Nobuaki Mutoh; Kiyasu-Zen'iti; Gisaku Nakamura

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 117 KB
Volume: 10
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.10003

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A double Dudeney set in K~n~ is a multiset of Hamilton cycles in K~n~ having the property that each 2‐path in K~n~ lies in exactly two of the cycles. A double Dudeney set in K~n~ has been constructed when n ≥ 4 is even. In this paper, we construct a double Dudeney set in K~n~ when n ≥ 3 is odd. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 195–206, 2002; Published online in Wiley InterScience (www.interscience.wiley.com) DOI 10.1002/jcd.10003

📜 SIMILAR VOLUMES

Vertex coverings by monochromatic paths

Vertex coverings by monochromatic paths and cycles

✍ A. Gyárfás 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

We survey some results on covering the vertices of 2-colored complete graphs by t w o paths or by t w o cycles Qf different color. W e show the role of these results i n determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs. ##

Small cycle double covers of products I:

Small cycle double covers of products I: Lexicographic product with paths and cycles

✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __

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

Hamilton cycle and Hamilton path extenda

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

✍ Štefko MiklaviČ; Primož Šparl 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is __n__‐__HC‐extendable__ if it contains a path of length __n__ and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is __weakly n__‐__HP‐

Recognizing triangle-free graphs with in

Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete

✍ Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 250 KB 👁 2 views

An induced path-cycle double cover (IPCDC) of a simple graph G is a family F Å {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ʝ F j x M, then F i ʝ F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in pr

Perfect double covers with paths of leng

Perfect double covers with paths of length four

✍ Heinrich, K.; Horak, P.; Wallis, W.; Yu, Qinglin 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 1 views

It is shown that for any 4-regular graph G there is a collection F of paths of length 4 such that each edge of G belongs to exactly two of the paths and each vertex of G occurs exactly twice as an endvertex of a path of y. This proves a special case of a conjecture of Bondy. 0 1996 John Wiley & Sons