𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Strong products of Kneser graphs

✍ Scribed by Sandi Klavžar; Uroš Milutinović

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
314 KB
Volume
133
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G [XI H be the strong product of graphs G and H. We give a short proof that

Kneser graphs are then used to demonstrate that this lower bound is sharp. We also prove that for every n > 2 there is an infinite sequence of pairs of graphs G and G' such that G' is not a retract of G while G' IXI K, is a retract of G ixI K..

📜 SIMILAR VOLUMES

Hamiltonian threshold for strong product
Hamiltonian threshold for strong products of graphs
✍ Daniel Král'; Ladislav Stacho 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## 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

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

Circular chromatic numbers of some reduc
Circular chromatic numbers of some reduced Kneser graphs
✍ Ko-Wei Lih; Daphne Der-Fen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

## Abstract The vertex set of the reduced Kneser graph KG~2~(__m,2__) consists of all pairs {__a,b__} such that __a, b__ε{1,2,…,__m__} and 2≤|__a__−__b__|≤__m__−2. Two vertices are defined to be adjacent if they are disjoint. We prove that, if __m__≥4 __and m__≠5, then the circular chromatic number

The Odd Girth of the Generalised Kneser
The Odd Girth of the Generalised Kneser Graph
✍ Tristan Denley 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 202 KB

Let X ϭ ͕ 1 , 2 , . . . , n ͖ be a set of n elements and let X ( r ) be the collection of all the subsets of X containing precisely r elements . Then the generalised Kneser graph K ( n , r , s ) (when 2 r Ϫ s р n ) is the graph with vertex set X ( r ) and edges AB for A , B X ( r ) with ͉ A ʝ B ͉ р