𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cartesian Products of Graphs and Metric Spaces

✍ Scribed by S. Avgustinovich; D. Fon-Der-Flaass

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
68 KB
Volume
21
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

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 isometric?' in the case of finite metric spaces.

In the proof we use uniqueness of cartesian decomposition of connected graphs; a known fact to which we give a new proof which is shorter and more transparent than existing ones.

πŸ“œ SIMILAR VOLUMES

Embedding Cartesian Products of Graphs i
Embedding Cartesian Products of Graphs into de Bruijn Graphs
✍ Thomas Andreae; Michael NΓΆlle; Gerald Schreiber πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 Γ— β€’ β€’ β€’ Γ— G m which are relevant for parallel computing, namely, to

Circular chromatic index of Cartesian pr
Circular chromatic index of Cartesian products of graphs
✍ Douglas B. West; Xuding Zhu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

## Abstract The __circular chromatic index__ of a graph __G__, written $\chi\_{c}'(G)$, is the minimum __r__ permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever __e__ and $e'$ are incident. Let $G = H$ β–‘ $C\_{2m +1}$, where β–‘ denotes Cartesian product

Embeddings of cartesian products of near
Embeddings of cartesian products of nearly bipartite graphs
✍ Bojan Mohar; TomaΕΎ Pisanski; Arthur T. White πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 384 KB

## Abstract Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is β€œclose” to a genus embedding for cartesian products, where each factor is β€œclose” to being bipartite. In specializi

Game coloring the Cartesian product of g
Game coloring the Cartesian product of graphs
✍ Xuding Zhu πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 186 KB

## Abstract This article proves the following result: Let __G__ and __G__β€² be graphs of orders __n__ and __n__β€², respectively. Let __G__^\*^ be obtained from __G__ by adding to each vertex a set of __n__β€² degree 1 neighbors. If __G__^\*^ has game coloring number __m__ and __G__β€² has acyclic chromat

s-strongly perfect cartesian product of
s-strongly perfect cartesian product of graphs
✍ Elefterie Olaru; Eugen Mǎndrescu πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 308 KB

## Abstract The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In β€œPerfect Product Graphs” (__Discrete Mathematics__, Vol. 20, 1977, pp. 177‐‐186), G. Ravindra and K. R.