Permutation group subdegrees and the common divisor graph (Q687625)

For a permutation group \(G\) acting transitively on the set \(\Omega\), its subdegrees are the cardinalities of the orbits of the action of a point stabilizer \(G_ \alpha\) on \(\Omega\). Because of the transitivity of \(G\), the set \(D = D(G,\Omega)\) of all subdegrees is well-defined, independently of the choice of \(\alpha \in \Omega\). The authors consider the case where all subdegrees are finite and investigate properties of the common-divisor graph \({\mathcal G}(D)\) corresponding to \(D = D(G,\Omega)\) which is defined as the undirected graph with vertex set \(D\) in which distinct integers \(x, y\in D\) are joined by an edge provided that \(x\) and \(y\) have a common divisor other than 1. It is easy to see that \(1 \in D\) and, therefore, \(\{1\}\) is a connected component of \({\mathcal G}(D)\). The authors' first main result states that the common-divisor graph \({\mathcal G}(D)\) has at most three connected components. Analysing this general situation with regard to the diameters of the connected components, the authors obtain two other main results: (i) If \({\mathcal G}(D)\) has just one nontrivial connected component, then its diameter is at most 4, and (ii) If \({\mathcal G}(D)\) has two nontrivial connected components, then one of them is a complete graph and the other has diameter at most 2. Finally, the authors show as well how the result (ii) can be strengthened under the condition that at least one of the nontrivial connected components is finite. Some other interesting results are presented together with several examples, as well.