𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finite invariant sets in infinite graphs

✍ Scribed by Norbert Polat

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
795 KB
Volume
158
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph G contains a nonempty finite subset which is invariant under any automorphism of G stabilizing A. Therefore any infinite connected graph not containing a ray has a finite set of vertices which is invariant under any automorphism. The same also holds for connected graphs with rays, containing no end-respecting subdivision of the dyadic tree, provided that there are at least three (resp. two) ends of maximal order (resp. and a vertex which cannot be finitely separated from one of them).

πŸ“œ SIMILAR VOLUMES

On finite fixed sets in infinite graphs
On finite fixed sets in infinite graphs
✍ H.A. Jung πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 762 KB

## An automorphism of a graph X is called a translation of X if it fixes no finite non-empty set of vertices of X. It is shown that a group G of automorphisms of the connected graph X fixes a finite non-empty set of vertices or ends of X if and only if any two translations of X in G have a common

Invariant Hamming graphs in infinite qua
Invariant Hamming graphs in infinite quasi-median graphs
✍ Marc Chastand; Norbert Polat πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 593 KB

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 g

Finite Separating Sets in Locally Finite
Finite Separating Sets in Locally Finite Graphs
✍ H.A. Jung; M.E. Watkins πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 386 KB

An \((m, n)\)-separator of an infinite graph \(\Gamma\) is a smallest finite set of vertices whose deletion leaves at least \(m\) finite components and at least \(n\) infinite components. It is shown that a vertex of \(\Gamma\) of finite valence belongs to only finitely many \((0,2)\)-separators. Va

Large k-preserving sets in infinite grap
Large k-preserving sets in infinite graphs
✍ Andreas Huck; Frank Niedermeyer; Saharon Shelah πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 715 KB

## Abstract Let __K__ be a cardinal. If __K__ Ο‡~0~, define K:= __K__. Otherwise, let __K__ := __K__ + 1. We prove a conjecture of Mader: Every infinite __K__‐connected graph __G__ = (__V, E__) contains a set __S__ βŠ† __V__ with |__S__| = |__V__| such that __G/S__ is __K__‐connected for all __S__βŠ† __

Cut-sets in infinite graphs and partial
Cut-sets in infinite graphs and partial orders
✍ A. Hajnal; N. Sauer πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 859 KB

Hajnal, A. and N. Sauer, Cut-sets in infinite graphs and partial orders. Discrete Mathematics 117 (1993) 113-125. The set S c V(U) is a cut-set of the vertex v of a graph 9 if v is not adjacent to any vertex in S and, for every maximal clique C of Q, ({v} u S) n C # 0. S is a cut-set of the element