Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Evolutionary Families of Sets. | Evolutionary Families of Sets C. H. C. Little and A. E. Campbell Massey University Palmerston North New Zealand allistercampbell@ Abstract A finite family of subsets of a finite set is said to be evolutionary if its members can be ordered so that each subset except the first has an element in the union of the previous subsets and also an element not in that union. The study of evolutionary families is motivated by a conjecture of Naddef and Pulleyblank concerning ear decompositions of 1-extendable graphs. The present paper gives some sufficient conditions for a family to be evolutionary. Received November 25 1998 Accepted January 29 2000. Mathematical Reviews Subject Numbers 03E05 05C70 1 Introduction The motivation for the concept of an evolutionary family of sets lies in a conjecture of Naddef and Pulleyblank 5 . This conjecture has recently been proved by Carvalho Lucchesi and Murty 2 . In order to explain this theorem we need several definitions concerning 1-factors of graphs. We adopt the terminology and notation found in 1 . In this paper graphs will be assumed to be finite and to have no loops or multiple edges. A 1-factor in such a graph G is a set F of edges such that jF n dv 1 for each v 2 VG. A graph is 1-extendable if for each edge e there is a 1-factor containing e. An alternating circuit is a circuit which is the sum symmetric difference of two 1-factors. A set S of alternating circuits is consanguineous with respect to a 1-factor F if each circuit in S has half its edges in F. Note that if G is a connected 1-extendable graph with more than one edge then every edge of G belongs to an alternating circuit. The alternating circuits span a subspace of the cycle space of G. This space is called the alternating space and is denoted by A G . Now let H be a subgraph of a graph G. An ear of G with respect to H is a path in G of odd length joining vertices of H but having no edges or internal vertices belonging to H. Let 1 THE .
