✦ LIBER ✦

Retracts of strong products of graphs

✍ Scribed by W. Imrich; S. Klavžar

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 750 KB
Volume: 109
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90285-n

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Strong products of Kneser graphs

✍ Sandi Klavžar; Uroš Milutinović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 314 KB

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,

Two remarks on retracts of graph product

Two remarks on retracts of graph products

✍ Sandi Klavžar 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 545 KB

KlavZar, S., Two remarks on retracts of graph products, Discrete Mathematics 109 (1992) 155-160. Let H be a bipartite graph and let G,, be the Mycielski graph with x(G) = n, n 3 4. Then the chromatic number of the strong product of G, by H is at most 2n -2. We use this result to show that there exi

Retracts of Infinite Hamming Graphs

✍ Marc Chastand 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A Hamming graph is a Cartesian product of complete graphs. We show that (finite or infinite) quasi-median graphs, which are a generalization of median graphs, are exactly the retracts of Hamming graphs. This generalizes a result of Bandelt (1984,

Absolute retracts of split graphs

✍ Sandi Klavžar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 663 KB

It is proved that a split graph is an absolute retract of split graphs if and only if a partition of its vertex set into a stable set and a complete set is unique or it is a complete split graph. Three equivalent conditions for a split graph to be an absolute retract of the class of all graphs are g

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

✍ 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