✦ LIBER ✦

Invariant Hamming graphs in infinite quasi-median graphs

✍ Scribed by Marc Chastand; Norbert Polat

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 593 KB
Volume: 160
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00151-l

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.

📜 SIMILAR VOLUMES

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,

Infinite median graphs, (0, 2)-graphs, a

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

✍ Hans-J. Bandelt; Henry Martyn Mulder 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB

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

Finite invariant sets in infinite graphs

✍ Norbert Polat 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 795 KB

The closure of a set A of vertices of an infinite graph G is defined as the set of vertices of G which cannot be finitely separated from A. A subset A of Y(G) is dispersed if it is finitely separated from any ray of G. It is shown that the closure of any dispersed set A of an infinite connected grap

Completely Transitive Codes in Hamming G

Completely Transitive Codes in Hamming Graphs

✍ Michael Giudici; Cheryl E. Praeger 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 169 KB

A code in a graph is a non-empty subset C of the vertex set V of . Given C, the partition of V according to the distance of the vertices away from C is called the distance partition of C. A completely regular code is a code whose distance partition has a certain regularity property. A special class

Finding Optimal Routings in Hamming Grap

Finding Optimal Routings in Hamming Graphs

✍ Tian Khoon Lim; Cheryl E. Praeger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 191 KB

A routing R in a graph consists of a simple path p uv from u to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p uv are shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving th

Infinite paths in planar graphs V, 3-ind

Infinite paths in planar graphs V, 3-indivisible graphs

✍ Xingxing Yu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 583 KB

## Abstract We prove Nash‐Williams' conjecture that every 4‐connected, 3‐indivisible, infinite, planar graph contains a spanning 2‐way infinite path. A graph is said to be 3‐indivisible if the deletion of any finite set of vertices results in at most two infinite components. © 2007 Wiley Periodical