Search

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. [ABSTRACT FROM AUTHOR]

Let G1⊗ G2 be the strong product of a k-extendable graph G1 and an l-extendable graph G2, and X an arbitrary set of vertices of G1⊗ G2 with cardinality 2[( k+1)( l+1)/2]. We show that G1⊗ G2− X contains a perfect matching. It implies that G1⊗ G2 is [( k+1)( l+1)/2]-extendable, whereas the Cartesian product of G1 and G2 is only ( k+ l+1)-extendable. As in the case of the Cartesian product, the proof is based on a lemma on the product of a k-extendable graph G and K2. We prove that G⊗ K2 is ( k+1)-extendable, and, a bit surprisingly, it even remains ( k+1)-extendable if we add edges to it. [ABSTRACT FROM AUTHOR]

Let X be a connected locally finite graph with vertex-transitive automorphism group. If X has polynomial growth then the set of all bounded automorphisms of finite order is a locally finite, periodic normal subgroup of AUT(X) and the action of AUT(X) on V(X) is imprimitive if X is not finite. If X has infinitely many ends, the group of bounded automorphisms itself is locally finite and periodic. [ABSTRACT FROM AUTHOR]

If Y is a finite graph then it is known that every sufficiently large group G has a Cayley graph containing an induced subgraph isomorphic to Y. This raises the question as to what is 'sufficiently large'. Babai and Sós have used a probabilistic argument to show that | G| > 9.5 | Y| suffices. Using a form of greedy algorithm we strengthen this to $$|G| > (2 + \sqrt 3 )|Y|^3 $$ . Some related results on finite and infinite groups are included. [ABSTRACT FROM AUTHOR]