Report

Packing Graphs with 4-Cycles 學生: 徐育鋒 指導教授: 高金美教授 2013組合新苗研討會 (2013.08.10 ~ 2013.08.11) 國立高雄師範大學 1. Definition 2. Known Results 3. 4-Regular Graphs 4. Main Results 5. Future Works Definition Definitions 1. A graph G is an order pair (V, E), where V is a non-empty set called a vertex set and E is a set of two-element subsets of V called an edge set. 2. degG(v) = the number of edges incident with a vertex v in G. 3. If all the vertices of a graph have the same degree r, then the graph is called r-regular. Definitions V = {v1, v2, v3, v4, v5, v6}. E = {v1v2, v1v3, v1v5, v1v6, v2v3, v2v4, v2v6, v3v4, v3v5, v4v5, v4v6, v5v6}. v6 v1 G: v5 v2 v4 v3 The graph G is 4-regular. Definitions 5. Cn = (v1,v2, ..., vn) : n-cycle v1 v5 v2 v4 v3 C5 = (v1, v2, v3, v4, v5) Definitions 6. Kn : the complete graph of order n. v1 v5 v2 v4 v3 K5 Definitions 7. KU,V : the complete bipartite graph with partite set U, V. If |U| = m, |V| = n, then KU,V can be denoted by Km,n. v1 v2 v3 v4 v5 v6 U = {v1, v2, v3}, V = {v4, v5, v6} KU,V = K3,3 Definitions Let = {H1, H2, , Hs} be a set of subgraphs of G. If E(H1) E(H2) E(Hs) = E(G) and E(Hi) E(Hj) = for i j, then we call is a decomposition (packing) of G. If Hi is isomorphic to a subgraph H of G for each i = 1, 2, , s, then we say that G has an H decomposition (H system) or is a H packing of G. If Hi is isomorphic to a subgraph H of G for each i = 1, 2, , s–1, then we say that G can be packed with H and leave Hs. That is, a Hanpacking of G – E(Hs). G –– {H E(H H decomposition. s}s)ishas v1 v2 v3 HG: 1: v4 v5 v6 v7 v8 H2: G =can decomposed intoofH1G. , H2. {Hbe 1, H 2} is a packing v9 v1 v2 v3 H1: v4 v5 v6 v1 v7 v2 v8 v9 v8 v9 v3 H2: v4 v5 v6 v7 ‘= {(v1, v5, v3, v6G ), (v has a2,4-cycle v5, v4), system. (v1, v7, v2, v9), (v2, v3, v7, v6), 1, v (v2, v4, v3, v8), (v1, v3, v9, v8)} is a 4-cycle packing of G. Cycle Decomposition Alspach Conjecture : Let 3 m1, m2, ..., mt n such that m1 + m2 + ... + mt = n(n–1)/2 for odd n (m1 + m2 + ... + mt = n(n–2)/2 for even n). Then Kn (Kn – F) can be decomposed into cycles C1, C2, ..., Ct such that Ci is a mi-cycle for i = 1, 2, ..., t. D. Bryant, D. Horsley and W. Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, arXiv:1204.3709v2 [math.CO], 2013. Cycle Decomposition D. Sotteau, Decomposition of Km,n (Km,n*) into cycles (circuits) of length 2k, J. Combin. Theory B, 30 (1981) 75.81. Theorem 1: There exists a 2k-cycle decomposition of Km,n if and only if each vertex has even degree, mn is divisible by 2k, and m, n k. Does there exist a 4-cycle system of Kn – E(G) for any 4-regular subgraph G of Kn? Known Results Known Results A. Kotzig, On decomposition of the complete graph into 4k-gons, Mat.-Fyz. Cas., 15 (1965), 227-233. Theorem 2: There exists a 4-cycle system of Kn if and only if n ≡ 1 (mod 8). Known Results B. Alspach and S. Marshall, Even cycle decompositions of complete graphs minus a 1-factor, J. Combin. Des., 2 (1994), 441-458. Theorem 3: There exists a 4-cycle system on Kn – F, where F is a 1-factor of Kn, if and only if n ≡ 0 (mod 2). Known Results H.-L. Fu and C. A. Rodger, Four-Cycle Systems with TwoRegular Leaves, Graphs and Comb., 17 (2001), 457-461. Theorem 4: Let F be a 2-regular subgraph of Kn. There exists a 4-cycle system of Kn – F if and only if n is odd and 4 divides the number of edges of Kn – F. Known Results C.-M. Fu, H.-L. Fu, C. A. Rodger and T. Smith, All graphs with Maximum degree three whose complements have 4-cycle Decompositions, Discrete Math., 308 (2008), 2901-2909. Theorem 5: Let G be a graph on n vertices, where n is even and (G) 3. Then there exists a 4-cycle system of Kn – E(G) if and only if (1) All vertices in G have odd degree, (2) 4 divides n(n–1)/2 – |E(G)|, and (3) G is not one of the two graphs of order 8 as follows. Let G be a 4-regular subgraph of Kn. Does there exist a 4-cycle system of Kn – E(G)? 4-Regular Graphs Some 4-regular graphs Question: Does there exist a 4-cycle system of Kn – E(K5) ? 1. n = 5, Yes! 2. n = 6, No! 3. n = 7, No! 4. n = ?, Yes! Question: Does there exist a 4-cycle system of Kn – E(K5) ? n 5 is odd and 4 | n(n – 1) / 2 – 10 ⇒ 4 | (n2 – n – 20) / 2 ⇒ 8 | (n – 4)(n – 5) ⇒ n 5 (mod 8). Question: Does there exist a 4-cycle system of Kn – E(K5) ? Answer: n 5 (mod 8), Yes! Let n = 8k + 5. K8k+5 – E(K5) = K8k+1 K4, 8k. ... K8k+1 K4, 8k Lemma 6: There exists a 4-cycle system of Kn – E(K5) if and only if n 5 (mod 8). Question: Does there exist a 4-cycle system of Kn – E(G) ? n 6 is odd and 4 | n(n – 1) / 2 – 12 ⇒ 4 | n(n – 1) / 2 ⇒ 8 | n(n – 1) ⇒ n 1 (mod 8). G: Question: Does there exist a 4-cycle system of K9 – E(G) ? G: K9 – E(G) : Question: Does there exist a 4-cycle system of K9 – E(G) ? Answer: Yes ! Question: Does there exist a 4-cycle system of Kn – E(G) ? Answer: n 1 (mod 8), Yes ! Let n = 8k + 1. G: Kn – E(G) = (K9 – E(G)) K8k–8 K8k–8,9 = (K9 – E(G)) K8k–7 K8k–8,8 Kn – E(G) K9 – E(G) G K8k–8 Lemma 7: There exists a 4-cycle system of Kn – E(G) if and only if n 1 (mod 8). G: Question: Does there exist a 4-cycle system of Kn – E(G)? n 6 is odd and 4 | n(n – 1) / 2 – 12 ⇒ 4 | n(n – 1) / 2 ⇒ 8 | n(n – 1) ⇒ n 1 (mod 8). G: Question: Does there exist a 4-cycle system of K9 – E(G)? Answer: No! G: K9 – E(G) : K9 – E(G) : Lemma 8: There exists a 4-cycle system of Kn – E(G) if and only if n 1 (mod 8) and n 17. G: Q(t) = {G | G is any connected 4-regular graph with t vertices}. t 5 |Q(t)| 1 6 7 8 1 2 6 9 10 11 16 59 265 12 13 1544 10778 s-reducible Definition 9: Let G be a 4-regular graph of order t. If there exists S V(G), |S| = s and a graph H where V(H) = N1(S) and E(H) E(G) = ∅ such that (G – S) H is 4-regular, then we call the graph G is s-reducible. S = {∞1} V(H) = N1(S) = {v1, v2, v3, v4} E(H) = {v1v4, v2v3} ∞1 v1 v2 v1 G – S: G: (G – S) H: v3 vv34 v5 v6 v2v1 v2 v3v4 v5 v6 G is 1-reducible. v5 v4 v6 3-reducible Theorem 10: Let t 8 and G be a 4-regular graph of order t. If G contains a component with at least 6 vertices, then G is 3-reducible. Sufficient Condition Theorem 11: Let G be a 4-regular of order t. If there exists a 4-cycle system of Kn – E(G), then (1) n ≣ 1 (mod 8), for t is even and (2) n ≣ 5 (mod 8), for t is odd. Construction G is 3-reducible 4-regular graph of order t. Kn – E(G) = [Kn–4 – E((G – S) H)] R. n ≣ 1 (mod 8), t is even. n ≣ 5 (mod 8), t is odd. Kn – E(G) (G – S) H H Kn–4 – E((G – S) H) S Main Results Main Theorem: Let G be any 4-regular graph with t vertices. There exists a 4-cycle system of Kn – E(G), if n is odd, 4 | n(n – 1)/2 – 2t, and (1) G is a vertex-disjoint union of t/5 copies of K5. (2) n (4t – 5)/3. (3) n > 9 for the following two graphs. Future Work Question 1. Let G be a 4-regular graph of order t. Does there exist a 4-cycle system of Kn – E(G) for t n < (4t – 5)/3? Question 2. Let G be a 4-regular graph of order t and t ≣ 5 (mod 8). Is G 5-reducible? Question 3. Let G be a 4-regular spanning subgraph of Kn. Does there exist a 4-cycle system of Kn – E(G) for n ≡ 5 (mod 8)? Thanks for your patient.