𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Infinite median graphs, (0, 2)-graphs, and hypercubes

✍ Scribed by Hans-J. Bandelt; Henry Martyn Mulder

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
450 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)graphs are hypercubes. No cardinality restrictions are made.

πŸ“œ SIMILAR VOLUMES

n-cubes and median graphs
n-cubes and median graphs
✍ Martyn Mulder πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 156 KB

## Abstract The n‐cube is characterized as a connected regular graph in which for any three vertices __u, v__, and __w__ there is a unique vertex that lies simultaneously on a shortest (__u, v__)‐path, a shortest (__v, w__)‐path, and a shortest (__w, u__)‐path.

On compact median graphs
On compact median graphs
✍ Tardif, Claude πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 715 KB

A median graph is called compact if it does not contain an isometric ray. This property is shown to be equivalent to the finite intersection property for convex sets. We show that a compact median graph contains a finite cube that is fixed by all of its automorphisms, and that each family of commuti

Small congestion embedding of graphs int
Small congestion embedding of graphs into hypercubes
✍ Matsubayashi, Akira; Ueno, Shuichi πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 103 KB πŸ‘ 1 views

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hype

Reverse mathematics and infinite traceab
Reverse mathematics and infinite traceable graphs
✍ Peter Cholak; David Galvin; Reed Solomon πŸ“‚ Article πŸ“… 2012 πŸ› John Wiley and Sons 🌐 English βš– 173 KB

## Abstract We analyze three applications of Ramsey’s Theorem for 4‐tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice t