𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Numerical invariants and the strong product of graphs

✍ Scribed by R.S Hales

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
420 KB
Volume
15
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Strong products of Kneser graphs
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,

Retracts of strong products of graphs
Retracts of strong products of graphs
✍ W. Imrich; S. KlavΕΎar πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 750 KB
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