Groups with an element permuting with finitely many of its conjugates

We study the problem as to which is the cardinality of connected components of the graph Γ_α, defined as follows. Let G be a group and a an element of G. The vertex set V(Γ_α) of the graph is the conjugacy class of elements,Cl _G(a), and two vertices x and y of the graph Γ_α are bridged by an edge iff x=y. If the intersectionC _G(a)∩Cl _G(a) is finite, Γ_α is locally finite. We prove that connected components of the locally finite graph Γ_α are finite in some classes of groups. Supported by RFFR grant No. 94-01-01084. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 543–551, September–October, 1996.     

Boundaries of random walks on graphs and groups with infinitely many ends

Consider an irreducible random walk {Z _n} on a locally finite graphG with infinitely many ends, and assume that its transition probabilities are invariant under a closed group Γ of automorphisms ofG which acts transitively on the vertex set. We study the limiting behaviour of {Z _n} on the spaceΩ of ends ofG. With the exception of a degenerate case,Ω always constitutes a boundary of Γ in the sense of Furstenberg, and {Z _n} converges a.s. to a random end. In this case, the Dirichlet problem for harmonic functions is solvable with respect toΩ. The degenerate case may arise when Γ is amenable; it then fixes a unique end, and it may happen that {Z _n} converges to this end. If {Z _n} is symmetric and has finite range, this may be excluded. A decomposition theorem forΩ, which may also be of some purely graph-theoretical interest, is derived and applied to show thatΩ can be identified with the Poisson boundary, if the random walk has finite range. Under this assumption, the ends with finite diameter constitute a dense subset in the minimal Martin boundary. These results are then applied to random walks on discrete groups with infinitely many ends.     

Deformations of complex structures on Γ/SL 2(C)

LetG be a connected complex semisimple Lie group. Let Γ be a cocompact lattice inG. In this paper, we show that whenG isSL ₂(C), nontrivial deformations of the canonical complex structure onX exist if and only if the first Betti number of the lattice Γ is non-zero. It may be remarked that for a wide class of arithmetic groups Γ, one can find a subgroup Γ′ of finite index in Γ, such that Γ′/[Γ′,Γ′] is finite (it is a conjecture of Thurston that this is true for all cocompact lattices inSL(2, C)). We also show thatG acts trivially on the coherent cohomology groupsH ⁱ(Γ/G, O) for anyi≥0.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

Groups containing an element that permutes with a finite number of its conjugates

We study a group G containing an element g such that C_G(g)∩g^G is finite. The nonoriented graph Γ is defined as follows. The vertex set of Γ is the conjugacy class g^G. Vertices x and y of the graph G are bridged by an edge iff x≠y and xy=yx. Let Γ₀ be some connected component of G. On a condition that any two vertices of Γ₀ generate a nilpotent group, it is proved that a subgroup generated by the vertex set of Γ₀ is locally nilpotent. Supported by the RF State Committee of Higher Education. Translated fromAlgebra i Logika, Vol. 37, No. 6, pp. 637–650, November–December, 1998.     

On graphs related to conjugacy classes of groups

LetG be a finite group. Attach toG the following two graphs: Γ — its vertices are the non-central conjugacy classes ofG, and two vertices are connected if their sizes arenot coprime, and Γ* — its vertices are the prime divisors of sizes of conjugacy classes ofG, and two vertices are connected if they both divide the size of some conjugacy class ofG. We prove that whenever Γ* is connected then its diameter is at most 3, (this result was independently proved in [3], for solvable groups) and Γ* is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. Using the method of that proof we give an alternative proof to Theorems in [1],[2],[6], namely that the diameter of Γ is also at most 3, whenever the graph is connected, and that Γ is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. As a result we conclude that both Γ and Γ* have at most two connected components. In [2],[3] it is shown that the above bounds are best possible. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at the Tel Aviv University under the supervision of Prof. Marcel Herzog.     

Černý’s conjecture and group representation theory

Let us say that a Cayley graph Γ of a group G of order n is a Černy Cayley graph if every synchronizing automaton containing Γ as a subgraph with the same vertex set admits a synchronizing word of length at most (n−1)². In this paper we use the representation theory of groups over the rational numbers to obtain a number of new infinite families of Černy Cayley graphs.     

Locally primitive Cayley graphs of finite simple groups

A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser G_a of a vertex α acts primitively on the set Г( α ) of vertices of Г adjacent to α. For a finite non-abelian simple group L and a Cayley subset S of L, suppose that L ⊴ G ⩽ Aut( L), and the Cayley graph Г = Cay ( L, S) is G-locally primitive. In this paper we prove that L is a simple group of Lie type, and either the valency of Г is an add prine divisor of |Out(L)|, orL =PΩ ₈ ⁺ (q) and Г has valency 4. In either cases, it is proved that the full automorphism group of Г is also almost simple with the same socle L.     

On critically connected digraphs

A digraph is called critically connected if it is connected, but the deletion of any vertex destroys the connectivity. We prove that every critically connected finite digraph has at least two vertices of outdegree one. As an application, we show that for n ≧ 2, there is no n-connected, non-complete, finite digraph such that the deletion of any n vertices results in a disconnected digraph.     

A characterization of alternating groups. II

Let G be a group. A subset X of G is called an A-subset if X consists of elements of order 3, X is invariant in G, and every two non-commuting members of X generate a subgroup isomorphic to A₄ or to A₅. Let X be the A-subset of G. Define a non-oriented graph Γ(X) with vertex set X in which two vertices are adjacent iff they generate a subgroup isomorphic to A₄. Theorem 1 states the following. Let X be a non-empty A-subset of G. (1) Suppose that C is a connected component of Γ(X) and H = 〈C〉. If H ∩ X does not contain a pair of elements generating a subgroup isomorphic to A₅ then H contains a normal elementary Abelian 2-subgroup of index 3 and a subgroup of order 3 which coincides with its centralizer in H. In the opposite case, H is isomorphic to the alternating group A(I) for some (possibly infinite) set I, |I| ≥ 5. (2) The subgroup 〈X^G〉 is a direct product of subgroups 〈C _α〉-generated by some connected components C _α of Γ(X). Theorem 2 asserts the following. Let G be a group and X⊆G be a non-empty G-invariant set of elements of order 5 such that every two non-commuting members of X generate a subgroup isomorphic to A₅. Then 〈XG〉 is a direct product of groups each of which either is isomorphic to A₅ or is cyclic of order 5. Supported by RFBR grant No. 05-01-00797; FP “Universities of Russia,” grant No. UR.04.01.028; RF Ministry of Education Developmental Program for Scientific Potential of the Higher School of Learning, project No. 511; Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1. __________ Translated from Algebra i Logika, Vol. 45, No. 2, pp. 203–214, March–April, 2006.     

Super-connectivity and super-edge-connectivity for some interconnection networks

Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs.     

Bounds on Laplacian eigenvalues related to total and signed domination of graphs

A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

A Generalization of the Gallai–Roy Theorem

 A well-known and essential result due to Roy ([4], 1967) and independently to Gallai ([3], 1968) is that if D is a digraph with chromatic number χ(D), then D contains a directed path of at least χ(D) vertices. We generalize this result by showing that if ψ(D) is the minimum value of the number of the vertices in a longest directed path starting from a vertex that is connected to every vertex of D, then χ(D) ≤ψ(D). For graphs, we give a positive answer to the following question of Fajtlowicz: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ(G) colors and for any vertex v∈V(G), there is a path P starting at v which represents all χ(G) colors. Received: May 20, 1999 Final version received: December 24, 1999     

On finite Moufang polygons

We show that a finite generalized polygon Γ is Moufang with respect to a groupG if and only if for every flag {x, y} of Γ, the subgroupG ₁(x, y) ofG fixing every element incident with one ofx, y acts transitively on the set of apartments containing the elementsu, x, y, w, whereu≠y (resp.w≠x) is an arbitrary element incident withx (resp.y). Research Associate at the National Fund of Scientific Research of Belgium. Research partially supported by NSF Grant DMS-8901904.     

Minimality and unique ergodicity of homogeneous actions

Consider a connected Lie groupG, a lattice Γ inG, a connected subgroupH ofG, and the adjoint representation Ad ofG on its Lie algebra g. Suppose that Ad(H) splits into a semidirect product of a reductive subgroup and the unipotent radical. We prove that the minimality of the leftH-action onG/Γ then implies its unique ergodicity. Simultaneously, we suggest a reduction of the study of finite ergodic measures for an arbitrary action (G/Γ,H), where the subgroupH∈G is connected and Γ∈G is discrete, to the case of an Abelian subgroupH. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 293–301, August, 1999.