tailieunhanh - Báo cáo toán học: "Counting two-graphs related to trees"

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: Counting two-graphs related to trees. | Counting two-graphs related to trees Peter J. Cameron Submitted October 19 1994 Accepted February 8 1995. Abstract. In an earlier paper I showed that the classes of pentagon-free two-graphs and of pentagon-and-hexagon-free two-graphs could be represented in terms of trees. This paper gives formulae for the numbers of labelled objects in each of these classes as well as the numbers of labelled reduced two-graphs in each class. The proofs use various enumeration results for trees. At least some of these results are well-known. To make the paper self-contained I have included proofs. MOS classification Primary 05 C 30 secondary 05 C 05 05 A 18. 1. Trees and two-graphs A two-graph is a pair X V where X is a set of points and V a set of 3-subsets of X having the property that any 4-subset of X contains an even number of members of V. Given a graph G on the vertex set X the set of 3-sets carrying an odd number of edges of G forms a two-graph on X. Every two-graph can be represented in this way and graphs G1 and G2 represent the same two-graph if and only if they are related by switching with respect to a set Y of vertices. This operation consists of interchanging adjacency and non-adjacency between Y and its complement X Y while leaving edges within or outside Y unchanged. When I speak of the pentagon and hexagon two-graphs below I mean the two-graphs obtained from the pentagon and hexagon graphs by this procedure. All this material can be found in Seidel 9 . Let X V be a two-graph. Define a relation on X by setting x y if either x y or no member of V contains both x and y. This is an equivalence relation. The two-graph is called reduced if the relation just defined is equality. In any two-graph the three points of any triple in V belong to different classes and replacing a point by an equivalent point does not affect membership in V that is is a congruence . Thus we have a canonical projection onto a reduced two-graph. The original two-graph is uniquely determined by .