On the generating graph of direct powers of a simple group

Let S be a nonabelian finite simple group and let n be an integer such that the direct product S ⁿ is 2-generated. Let Γ(S ⁿ ) be the generating graph of S ⁿ and let Γ _n (S) be the graph obtained from Γ(S ⁿ ) by removing all isolated vertices. A recent result of Crestani and Lucchini states that Γ _n (S) is connected, and in this note we investigate its diameter. A deep theorem of Breuer, Guralnick and Kantor implies that diam(Γ ₁(S))=2, and we define Δ(S) to be the maximal n such that diam(Γ _n (S))=2. We prove that Δ(S)≥2 for all S, which is best possible since Δ(A ₅)=2, and we show that Δ(S) tends to infinity as |S| tends to infinity. Explicit upper and lower bounds are established for direct powers of alternating groups.     

Representing abstract groups by powers of a graph

We deal with the problem of representing several abstract groups simultaneously by one graph as automorphism groups of its powers. We call subgroups Γ₁,…, Γ_n of a finite group Γ representable iff there is a graph G and an injective mapping φ from ∪_i=1ⁿΓ_i into the symmetric group on V(G) such that for i=1,…, n φ|_Γi is a monomorphism onto Aut Gⁱ. We give a necessary and a sufficient condition for groups being representable, the latter implying, e.g., that finite groups Γ₁≤…≤Γ_n are representable.     

The generating graph of finite soluble groups

For a finite group G, let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. We prove that if G is soluble, then the non-isolated vertices of Γ(G) belong to a unique connected component.     

The generating graph of some monolithic groups

For a finite group G let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. We look for conditions on the positive integer m that ensure that Γ(G) contains a Hamiltonian cycle when G=S?Cm is the wreath product of a finite simple group S and a cyclic group of order m.     

Products of powers in finite simple groups

LetG be a group. For a natural numberd≥1 letG ^d denote the subgroup ofG generated by all powersa ^d ,a∈G. A. Shalev raised the question if there exists a functionN=N(m, d) such that for anm-generated finite groupG an arbitrary element fromG ^d can be represented asa ₁ ^d ...a _N ^d ,a _i ∈G. The positive answer to this question would imply that in a finitely generated profinite groupG all power subgroupsG ^d are closed and that an arbitrary subgroup of finite index inG is closed. In [5,6] the first author proved the existence of such a function for nilpotent groups and for finite solvable groups of bounded Fitting height. Another interpretation of the existence ofN(m, d) is definability of power subgroupsG ^d (see [10]). In this paper we address the question for finite simple groups. All finite simple groups are known to be 2-generated. Thus, we prove the following: THEOREM:There exists a function N=N(d) such that for an arbitrary finite simple group G either G ^d =1 orG={a ₁ ^d ...a _N ^d |a _i ∈G}. The proof is based on the Classification of finite simple groups and sometimes resorts to a case-by-case analysis.     

Pseudosimilar vertices in a graph

Dissimilar vertices whose removal leaves isomorphic subgraphs are called pseudosimilar. We construct infinite families of graphs having identity automorphism group, yet every vertex is pseudosimilar to some other vertex. Potential impact on the Reconstruction Conjecture is considered. We also construct, for each n, graphs containing a subset of n vertices which are mutually pseudosimilar. the analogous problem for mutually pseudosimilar edges is introduced.     

On the growth of generating sets for direct powers of semigroups

For a semigroup S its d-sequence is d(S)=(d ₁,d ₂,d ₃,…), where d _i is the smallest number of elements needed to generate the ith direct power of S. In this paper we present a number of facts concerning the type of growth d(S) can have when S is an infinite semigroup, comparing them with the corresponding known facts for infinite groups, and also for finite groups and semigroups.     

The least eigenvalue of a graph with cut vertices

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound.     

Upper bounds on the sum of powers of the degrees of a simple planar graph

For a simple planar graph G and a positive integer k, we prove the upper bound 2(n ? 1)^k + 4^k(n ? 4) + 2·3^k ? 2((δ + 1)^k ? δ^k)(3n ? 6 ? m) on the sum of the kth powers of the degrees of G, where n, m, and δ are the order, the size, and the minimum degree of G, respectively. The bound is tight for all m with 0?3n ? 6 ? m≤?n/2? ? 2 and δ = 3. We also present upper bounds in terms of order, minimum degree, and maximum degree of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:112‐123, 2011     

On vertices of exterior powers of the natural simple module for the symmetric group in odd characteristic

We determine the vertices of certain exterior powers of the natural simple -module in odd characteristic p and, in particular, of the simple -module for the case n = pw and w ≢ 1 (mod p). Received: 22 February 2007     

Cycles through specified vertices of a graph

We prove that ifS is a set ofk−1 vertices in ak-connected graphG, then the cycles throughS generate the cycle space ofG. Moreover, whenk≧3, each cycle ofG can be expressed as the sum of an odd number of cycles throughS. On the other hand, ifS is a set ofk vertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs of high connectivity.     

Abelian groups determined by subgroup lattices of direct powers

In this short note, we showthat the class of abelian groups determined by the subgroup lattice of their direct n-powers is exactly the class of the abelian groups which share the n-root property. As applications we answer in the negative a (semi)conjecture of Pálfy and solve a more general problem. Received: 24 February 2005     

Strongly simplicial vertices of powers of trees

For a tree T and an integer k?1, it is well known that the kth power T^k of T is strongly chordal and hence has a strong elimination ordering of its vertices. In this note we obtain a complete characterization of strongly simplicial vertices of T^k, thereby characterizing all strong elimination orderings of the vertices of T^k.     

On covering vertices of a graph by trees

The purpose of this paper is to initiate study of the following problem: Let G be a graph, and k?1. Determine the minimum number s of trees T₁,…,T_s, Δ(T_i)?k,i=1,…,s, covering all vertices of G. We conjecture: Let G be a connected graph, and k?2. Then the vertices of G can be covered by edge-disjoint trees of maximum degree ?k. As a support for the conjecture we prove the statement for some values of δ and k.     

The minimum number of vertices of a simple polytope

Ad-polytope is ad-dimensional set that is the convex hull of a finite number of points. Ad-polytope is simple provided each vertex meets exactlyd edges. It has been conjectured that for simple polytopes {fx121-1} wheref _i is the number ofi-dimensional faces of the polytope. In this paper we show that inequality (i) holds for all simple polytopes. Research supported by N.S.F. Grant GP-19221.