完全三分图分割成星状图的探讨.ppt

20110627 2011年圖論與組合學研討會暨第六屆海峽兩岸圖論與組合學研討會 From Steiner Triple Systems to 3-sun systems Join work with Y.-L. Lin(林遠隆), N.-H. Jhuang (莊柟樺),H.-M. Song (宋曉明) Outline Steiner triple system 3-sun systems Embed a cyclic Steiner triple system into a 3-sun system Steiner triple system A Steiner triple system (of order n) STS(n) is a 2-(n,3,1) design, A collection of 3-subsets of an n-set such that any pair of elements of the n-set is contained in a unique one among these 3-sets. As was shown by Kirkman, a Steiner triple system of order n exists if and only if either n = 0, 1, or n congruent to 1 or 3 (mod 6). STS(n) Examples of Steiner triple systems of small orders are (1) S1={{1,2,3}} (2) S2={{1,2,3},{1,4,5},{1,6,7},  {2,4,6},{2,5,7},{3,4,7},{3,5,6}} (3) S3={{1,2,3}, {4,5,6}, {7,8,9},  {1,4,7}, {2,5,8}, {3,6,9}, {1,5,9}, {2,6,7}, {3,4,8}, {1,6,8}, {2,4,9}, {3,4,6}}  STS(n) STS(7) STS(9) Decomposition Let G be a simple graph. A decomposition D of G is a collection of edge-disjoint subgraphs H1, H2, …, Hm of G such that every edge of G belongs to exactly one Hj for j = 1,2,3,…,m. T-decomposition If each member of D is isomorphic to a graph T, then D is called a T-decomposition of G. A T-decomposition of G is also called a (G,T)-design. A STS(n) corresponds to a C3-decomposition of Knor 3-cycle system of order n. A STS(n) is a (Kn,C3)-design or a (Kn,K3)-design. N-Sun graph Let Cn be an n-cycle (v1, v2, v3,…, vn). Add n pendent edges v1w1, v2w2, v3w3,…, vnwn to Cn. The resulting graph on 2n vertices is called an n-sun graph, denoted by S(Cn) = [(v1, v2, v3,…, vn), w1, w2, w3,…, wn] . Motivation In 2008, Anitha and Lekshmi proved that If k is odd, then K2k can be decomposed into k – 1 k-sun graphs and a perfect matching. If k is even, then K2k can be decomposed into k – 2 k-sun graphs, a perfect matching and a Hamilton cyce. 3-sun graph What is the value of n such that Kn can b