𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian threshold for strong products of graphs

✍ Scribed by Daniel Král'; Ladislav Stacho

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
161 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that the strong product of any at least ${({\rm ln}}, {2})\Delta+{O}(\sqrt{\Delta})$ non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ⌊(ln 2)D⌋ stars K~1,D~ is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008

📜 SIMILAR VOLUMES

Hamiltonian decompositions of strong pro
Hamiltonian decompositions of strong products
✍ Fan, Cong; Liu, Jiuqiang 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

It is shown that if both G 1 and G 2 are Hamiltonian decomposable, then so is their strong product.

The graphs for which all strong orientat
The graphs for which all strong orientations are hamiltonian
✍ Martin Grötschel; Frank Harary 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.

NZ-flows in strong products of graphs
NZ-flows in strong products of graphs
✍ Wilfried Imrich; Iztok Peterin; Simon Špacapan; Cun-Quan Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

We prove that the strong product G 1 G 2 of G 1 and G 2 is Z 3 -flow contractible if and only if G 1 G 2 is not T K 2 , where T is a tree (we call T K 2 a K 4 -tree). It follows that G 1 G 2 admits an NZ 3-flow unless G 1 G 2 is a K 4 -tree. We also give a constructive proof that yields a polynomial

Hamilton cycles in strong products of gr
Hamilton cycles in strong products of graphs
✍ Daniel Král'; Jana Maxová; Robert Šámal; Pavel Podbrdský 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB

## Abstract We prove that the strong product of any __n__ connected graphs of maximum degree at most __n__ contains a Hamilton cycle. In particular, __G__^Δ(__G__)^ is hamiltonian for each connected graph __G__, which answers in affirmative a conjecture of Bermond, Germa, and Heydemann. © 2005 Wile

Families of graphs complete for the stro
Families of graphs complete for the strong perfect graph Conjecture
✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true