tailieunhanh - Báo cáo toán học: "A Small Trivalent Graph of Girth 14"

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í toán học quốc tế đề tài: A Small Trivalent Graph of Girth 14. | A Small Trivalent Graph of Girth 14 Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 g-exoo@ Submitted January 5 2001 Accepted March 11 2002. Abstract We construct a graph of order 384 the smallest known trivalent graph of girth 14. AMS Subject Classifications 05D25 05D35 In this note we use a construction technique that can be viewed as a kind of generalized Cayley graph. The vertex set V of such a graph consists of the elements in multiple copies of some finite group G. The action of G on V is determined by the regular action on each of the copies of G. This induces an action on the edges of the complete graph on V. The edge set of the graph we construct is the union of certain of these orbits. The particular graph we describe is a trivalent graph of girth 14 and order 384. It is constructed as above using a permutation group G of order 48 the group generated by the following two permutations. 1 33 37 6 9 44 8 19 23 18 22 34 2 5 40 4 12 16 11 15 27 48 26 30 3 25 41 24 14 39 13 38 29 10 28 46 7 32 45 31 21 43 20 42 36 17 35 47 1 26 20 25 8 12 7 38 2 21 24 9 11 35 10 22 3 32 48 19 13 42 4 33 5 6 28 31 15 18 14 17 16 34 41 47 30 44 29 43 23 40 45 39 37 27 36 46 The permutation representation so generated is in fact a regular representation of the underlying abstract group as can be verified using GAP 4 . THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 N3 1 Now let the vertex set of our graph be V i I 0 i 384 and dehne the action of Q on V as follows. For each a 2 Q dehne a permutation a on V by a v ơ v mod 48 48 _v 48_ for all v 2 V. To construct our graph we choose a set of unordered vertex pairs u v and for each a 2 Q we add the edge a u a v to the graph. To construct the required graph we use the following 12 vertex pairs which give us a set of 12 X 48 576 edges. 0 115 48 140 0 126 48 173 0 282 48 339 144 199 192 362 144 261 240 289 192 312 288 360 The construction guarantees that the .