Symmetric bowtie decompositions of the complete graph

Simona Bonvicini ; Beatrice Ruini

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

Given a bowtie decomposition of the complete graph $K_v$ admitting an automorphism group $G$ acting transitively on the vertices of the graph, we give necessary conditions involving the rank of the group and the cycle types of the permutations in $G$. These conditions yield non–existence results for instance when $G$ is the dihedral group of order $2v$, with $v\equiv 1, 9\pmod{12}$, or a group acting transitively on the vertices of $K_9$ and $K_{21}$. Furthermore, we have non–existence for $K_{13}$ when the group $G$ is different from the cyclic group of order $13$ or for $K_{25}$ when the group $G$ is not an abelian group of order $25$. Bowtie decompositions admitting an automorphism group whose action on vertices is sharply transitive, primitive or $1$–rotational, respectively, are also studied. It is shown that if the action of $G$ on the vertices of $K_v$ is sharply transitive, then the existence of a $G$–invariant bowtie decomposition is excluded when $v\equiv 9\pmod{12}$ and is equivalent to the existence of a $G$–invariant Steiner triple system of order $v$. We are always able to exclude existence if the action of $G$ on the vertices of $K_v$ is assumed to be $1$–rotational. If, instead, $G$ is assumed to act primitively then existence can be excluded when $v$ is a prime power satisfying some additional arithmetic constraint.

Détail

DOI : 10.37236/373

Classification : 05C25, 05B07, 20B25