Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: More Forbidden Minors for Wye-Delta-Wye Reducibility. | More Forbidden Minors for Wye-Delta-Wye Reducibility Yaming Yu Department of Statistics University of California Irvine CA 92697 USA yamingy@ Submitted Mar 5 2005 Accepted Jan 18 2006 Published Jan 25 2006 Mathematics Subject Classifications 05C75 05C83 Abstract A graph is YAY reducible if it can be reduced to isolated vertices by a sequence of series-parallel reductions and YAY transformations. It is still an open problem to characterize YAY reducible graphs in terms of a finite set of forbidden minors. We obtain a characterization of such forbidden minors that can be written as clique k-sums for k 1 2 3. As a result we show constructively that the total number of forbidden minors is more than 68 billion up to isomorphism. 1 Introduction We follow the terminology of Archdeacon et al. 1 . The graphs under consideration are finite undirected but may have loops or multiple edges. The series-parallel reductions are defined by the following four operations Loop reduction Delete a loop. Degree-one reduction Delete a degree-one vertex and its incident edge. Series reduction Delete a degree-two vertex y and its two incident edges xy and yz and add the new edge xz. Parallel reduction Delete one of a pair of parallel edges. The class of graphs that can be reduced to isolated vertices by these four reductions is called series-parallel reducible. Disconnected graphs are allowed for convenience. The YA and AY transformations are defined as follows THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R7 1 YA transformation Delete a degree-three vertex w and its three incident edges wx wy and wz and add three edges xy yz and xz. AY transformation Delete the three edges of a triangle delta xyz and add a new vertex w and three new edges wx wy and wz. Two graphs that can be obtained from each other by a sequence of YAY transformations are called YAY equivalent. The class of graphs that can be reduced to isolated vertices by the above six reductions transformations is called YAY .
