𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cartesian products of trees and paths

✍ Scribed by Bandelt, Hans-J�rgen; Burosch, Gustav; Laborde, Jean-Marie

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
581 KB
Volume
22
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We characterize the (weak) Cartesian products of trees among median graphs by a forbidden 5-vertex convex subgraph. The number of tree factors (if finite) is half the length of a largest isometric cycle. Then a characterization of Cartesian products of n trees obtains in terms of isometric cycles and intervals. Finally we investigate to what extent the proper intervals determine the product structure.

📜 SIMILAR VOLUMES

On optimal orientations of Cartesian pro
On optimal orientations of Cartesian products of even cycles and paths
✍ Koh, K. M.; Tay, E. G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

For a graph G , let D ( G ) be the family of strong orientations of G , and define d ៝ ( G ) Å min{d(D)ÉD √ D(G)}, where d(D) is the diameter of the digraph D. In this paper, we evaluate the values of d ៝ (C 2n 1

On the crossing numbers of Cartesian pro
On the crossing numbers of Cartesian products with trees
✍ Drago Bokal 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

## Abstract Zip product was recently used in a note establishing the crossing number of the Cartesian product __K__~1~,__n__ □ __P__~m~. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding metho

Walks and paths in trees
Walks and paths in trees
✍ Béla Bollobás; Mykhaylo Tyomkyn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negativ

Cartesian Products of Graphs and Metric
Cartesian Products of Graphs and Metric Spaces
✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr

The Cartesian product of hypergraphs
The Cartesian product of hypergraphs
✍ Lydia Ostermeier; Marc Hellmuth; Peter F. Stadler 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs