Search

Let T be a finite or infinite tree and m the minimum number of vertices moved by the non-identity automorphisms of T. We give bounds on the maximum valence d of T that assure the existence of a vertex coloring of T with two colors that is preserved only by the identity automorphism. For finite m we obtain the bound d ≤ 2 m / 2 when T is finite, and d ≤ 2 (m - 2) / 2 + 2 when T is infinite. For countably infinite m the bound is d ≤ 2 m. This relates to a question of Babai, who asked whether there existed a function f(d) such that every connected, locally finite graph G with maximum valence d has a 2-coloring of its vertices that is only preserved by the identity automorphism if the minimum number m of vertices moved by each non-identity automorphisms of G is at least m ≥ f (d) . Our results give a positive answer for trees. The trees need not be locally finite, their maximal valence can be 2 ℵ 0 . For finite m we also extend our results to asymmetrizing trees by more than two colors. [ABSTRACT FROM AUTHOR]

This note presents a new, elementary proof of a generalization of a theorem of Halin to graphs with unbounded degrees, which is then applied to show that every connected, countably infinite graph G, with $$\aleph _0 \le |{\text {Aut}}(G)| < 2^{\aleph _0}$$ and subdegree-finite automorphism group, has a finite set F of vertices that is setwise stabilized only by the identity automorphism. A bound on the size of such sets, which are called distinguishing, is also provided. To put this theorem of Halin and its generalization into perspective, we also discuss several related non-elementary, independent results and their methods of proof. [ABSTRACT FROM AUTHOR]

This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph G is edge-transitive if and only if it is vertex-transitive and if G is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph H, or if G is the weak Cartesian power of a connected, bipartite, edge-transitive graph H that is not vertex-transitive. [ABSTRACT FROM AUTHOR]

A group $$A$$ acting faithfully on a set $$X$$ is $$2$$ - distinguishable if there is a $$2$$ -coloring of $$X$$ that is not preserved by any nonidentity element of $$A$$ , equivalently, if there is a proper subset of $$X$$ with trivial setwise stabilizer. The motion of an element $$a \in A$$ is the number of points of $$X$$ that are moved by $$a$$ , and the motion of the group $$A$$ is the minimal motion of its nonidentity elements. When $$A$$ is finite, the Motion Lemma says that if the motion of $$A$$ is large enough (specifically at least $$2\log _2 |A|$$ ), then the action is $$2$$ -distinguishable. For many situations where $$X$$ has a combinatorial or algebraic structure, the Motion Lemma implies that the action of $$\mathrm{Aut }(X)$$ on $$X$$ is 2-distinguishable in all but finitely many instances. We prove an infinitary version of the Motion Lemma for countably infinite permutation groups, which states that infinite motion is large enough to guarantee $$2$$ -distinguishability. From this, we deduce a number of results, including the fact that every locally finite, connected graph whose automorphism group is countably infinite is $$2$$ -distinguishable. One cannot extend the Motion Lemma to uncountable permutation groups, but nonetheless we prove that (under the permutation topology) every closed permutation group with infinite motion has a dense subgroup which is $$2$$ -distinguishable. We conjecture an extension of the Motion Lemma which we expect holds for a restricted class of uncountable permutation groups, and we conclude with a list of open questions. The consequences of our results are drawn for orbit equivalence of infinite permutation groups. [ABSTRACT FROM AUTHOR]

This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs. [ABSTRACT FROM AUTHOR]

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]

For every integer d>2 we give an explicit construction of infinitely many Cayley graphs X of degree d with n( X) vertices and girth >0.4801...(log n( X))/log ( d−1)−2. This improves a result of Margulis. [ABSTRACT FROM AUTHOR]

It is shown that there exist exactly twenty products of graphs defined on the Cartesian product of the vertex sets of the factors where the adjacencies of the vertices only depend on the adjacencies in the factors. [ABSTRACT FROM AUTHOR]

A graph X is called a graphical regular representation ( GRR) of a group G if the automorphism group of X is regular and isomorphic to G. Watkins and Nowitz have shown that the direct product G× H of two finite groups G and H has a GRR if both factors have a GRR and if at least one factor is different from the cyclic group of order two. We give a new proof of this result, thereby removing the restriction to finite groups. We further show that the complement X′ of a finite or infinite graph X is prime with respect to cartesian multiplication if X is composite and not one of six exceptional graphs. [ABSTRACT FROM AUTHOR]

An der Rechenanlage der Technischen Hochschule Wien wurden im Jahre 1966 von Gerd Baron alle zusammenhängenden kubischen Graphen mit zehn Knoten bestimmt. Dabei erhob sich die Frage, ob man diese Graphen nicht auch ohne Komputer auf einfache Art bestimmen könne. Die Struktur dieser 19 verschiedenen Graphen legte eine Klasseneinteilung nach der Zahl und Lage der auftretenden Dreiecke nahe. Diese Einteilung führt auch tatsächlich zum Ziel, wie in dieser Arbeit gezeigt werden soll. Da die Diagramme dieser Graphen von Balaban bereits in [1] und [2] veröffentlicht wurden, verzichten wir auf Abbildungen. In den erwähnten Arbeiten wird nicht beschrieben, wie die zehnpunktigen kubischen Graphen bestimmt wurden. Wir betrachten nur ungerichtete Graphen ohne Mehrfachkanten und Schlingen. Ist G ein Graph, so verstehen wir unter V(G) die Knotenmenge von G, unter E(G) die Kantenmenge von G, und unter | G| die Kardinalzahl von V(G). Ist weiters K ein Teilgraph von G, so sei G - K der gesättigte Teilgraph H von G mit der Knotenmenge V(H) = V(G) - V(K). Ein kubischer Graph ist ein regulärer Graph vom Grad drei. Offensichtlich enthält jeder kubische Graph Kreise. [ABSTRACT FROM AUTHOR]