×

Hamiltonian cycles in the generating graphs of finite groups. (English) Zbl 1223.20058

For a finite group \(G\) let \(\Gamma(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\). Such graph \(\Gamma(G)\) is called the generating graph of \(G\). Many deep results about finite simple groups \(G\) can equivalently be stated as theorems about \(\Gamma(G)\). In this paper those finite groups \(G\) are considered for which \(\Gamma(G)\) contains a Hamiltonian cycle.
First of all, the authors prove that when \(G\) is a solvable group of order at least \(4\) with the property that \(G/N\) is cyclic for every non-trivial normal subgroup \(N\) of \(G\), it is possible just to exhibit a Hamiltonian cycle in the graph \(\Gamma(G)\). In Sections 4 and 5 it is shown that the generating graphs \(\Gamma(G)\) and \(\Gamma(A_n)\) satisfy Pósa’s criterion for every sufficiently large finite simple group \(G\) of Lie type and for every sufficiently large alternating group \(A_n\), respectively, and hence each of them contains a Hamiltonian cycle. Indeed, in Sections 6 it is shown that for every sufficiently large symmetric group \(S_n\) the graph \(\Gamma(S_n)\) contains a Hamiltonian cycle using Chvátal’s criterion. Finally, the authors prove the following theorem: for every sufficiently large non-Abelian finite simple group \(S\), the graph \(\Gamma(S\wr C_m)\) contains a Hamiltonian cycle, where \(m\) denotes a prime power.
Based on the results of this paper and some GAP computations concerning Hamiltonian cycles in the generating graphs of “small” groups and the sporadic simple groups, the authors propose the following conjecture: let \(G\) be a finite group with at least four elements, then the graph \(\Gamma(G)\) contains a Hamiltonian cycle if and only if \(G/N\) is cyclic for all non-trivial normal subgroups \(N\) of \(G\).

MSC:

20P05 Probabilistic methods in group theory
20D60 Arithmetic and combinatorial problems involving abstract finite groups
20F05 Generators, relations, and presentations of groups
05C45 Eulerian and Hamiltonian graphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20D06 Simple groups: alternating groups and groups of Lie type

Software:

GAP
PDFBibTeX XMLCite
Full Text: DOI