tailieunhanh - Báo cáo toán học: "Symmetric bowtie decompositions of the complete graph"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Symmetric bowtie decompositions of the complete graph. | Symmetric bowtie decompositions of the complete graph Simona Bonvicini Dipartimento di Scienze e Metodi dell Ingegneria Via Amendola 2 Pad. Morselli 42100 Reggio Emilia Italy Beatrice Ruini Dipartimento di Matematica Pura ed Applicata Via Campi 213 b 41125 Modena Italy Submitted Nov 23 2009 Accepted Jul 7 2010 Published Jul 20 2010 Mathematics Subject Classification 05C25 05B07 20B25 Abstract Given a bowtie decomposition of the complete graph Kv 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 1 9 mod 12 or a group acting transitively on the vertices of K9 and K21. Furthermore we have non-existence for K13 when the group G is different from the cyclic group of order 13 or for K25 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 Kv is sharply transitive then the existence of a G-invariant bowtie decomposition is excluded when v 9 mod 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 Kv 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. 1 Introduction A bowtie is a simple graph with 5 vertices and 6 edges consisting of a pair of edge-disjoint cycles called triples sharing one vertex. A bowtie decomposition of the complete graph THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R101 1 Kv V E is a partition Bv of the .