توصيفگر ها :
تجزيه , بستهبندي , گراف چندگانه كامل , ابرگراف چندگانهk-يكنواخت كامل , حدس السپك , حدس تارسي , حدس برموند , دور برج , مسير برج , تطابق برج , ستاره برج , عامل-ثابت , رأس-انتقالي , گراف دوري , گراف كيلي روي گروه دووجهي
چكيده انگليسي :
Some problems on decomposition of graphs and uniform hypergraphs AFSANEH KHODADADPOUR a khodadadpour@math iut ac ir September 18 2019 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Gholamreza Omidi romidi@cc iut ac irAdvisor Dr Ramin Javadi rjavadi@cc iut ac ir2000 MSC 05C25 20B25 05C60Keywords Decomposition Packing complete multigraph complete k uniform multi hypergraph Alspach s conjecture Tarsi s conjecture Bermond s conjecture Berge cycle Berge path Berge matching Berge star Factor invariant Vertex transitive Circulant graph Cayley graph on dihedral group Abstract This thesis deals with decomposition on graphs and uniform hypergraphs Bryant in 2010 verifying aconjecture by Tarsi proved that the obvious necessary conditions for packing pairwise edge disjoint pathsof arbitrary lengths in complete multigraph are also sufficient In 2015 a well known conjecture byAlspach which provided the necessary and sufficient conditions for the decomposition of the completegraph or complete graph minus an 1 factor into cycles of arbitrary lengths was completely solved byBryant Horsley and Peterson Moreover Bryant Horsley Maenhaut and Smith generalized Alspach sconjecture for the complete multigraphs In this thesis we obtain the necessary and sufficient conditionsfor packing edge disjoint cycles of arbitrary lengths in complete multigraph or complete multigraphminus an 1 factor In 2014 K hn and Osthus verifying a conjecture by Bermond et al proved the k necessary and sufficient conditions for the decomposition of the complete hypergraph Kn into HamiltonBerge cycles as long as n is not very small In this thesis by using above results and as a generalizing of Bermond et al s conjecture we investigate k the problem of the decomposition of the complete uniform multi hypergraph Kn into Berge cycles andBerge paths of arbitrary given lengths In particular we show that for every integer 1 n 108 and k 3 k n Kn can be decomposed into Berge cycles and Berge paths of arbitrary lengths providedthat the obvious necessary conditions hold In the following we provide two other generalized problem of Bermond et al s conjecture One problem k is the decomposition of Kn into Berge matchings of arbitrary lengths In this regard we investigatethe decomposition of complete multigraph into matchings of arbitrary lengths Then applying this result k we obtain the necessary and sufficient conditions for the decomposition of Kn into matchings ofarbitrary lengths k Another problem is the decomposition of Kn into Berge stars of arbitrary lengths In this regard weinvestigate the decomposition of complete multigraph into stars with the arbitrary lengths However In1996 Lin and Shyu gave necessary and sufficient conditions for the existence of a decomposition of a Kn we show that for 2 the problem of theinto stars of arbitrary lengths using 3 P Pdecomposition of complete multigraph into stars with the arbitrary lengths is NP complete in general Cameron and Horsley showed that it becomes tractable if we place a strong enough upper bound on themaximum amount of the lengths of the stars In the following we investigate the problem when the
