DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kang, Dong Yeap | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.date.accessioned | 2020-02-05T02:20:05Z | - |
dc.date.available | 2020-02-05T02:20:05Z | - |
dc.date.created | 2020-02-04 | - |
dc.date.created | 2020-02-04 | - |
dc.date.created | 2020-02-04 | - |
dc.date.created | 2020-02-04 | - |
dc.date.created | 2020-02-04 | - |
dc.date.issued | 2020-03 | - |
dc.identifier.citation | JOURNAL OF COMBINATORIAL THEORY SERIES B, v.141, no.1, pp.31 - 71 | - |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://hdl.handle.net/10203/272065 | - |
dc.description.abstract | We prove that every strongly 10(50)t-connected tournament contains all possible 1-factors with at most t components and this is best possible up to constant. In addition, we can ensure that each cycle in the 1-factor contains a prescribed vertex. This answers a question by Kuhn, Osthus, and Townsend. Indeed, we prove more results on partitioning tournaments. We prove that a strongly Omega(k(4)tq)-connected tournament admits a vertex partition into t strongly k-connected tournaments with prescribed sizes such that each tournament contains q prescribed vertices, provided that the prescribed sizes are Omega(n). This result improves the earlier result of Kuhn, Osthus, and Townsend. We also prove that for a strongly Omega(t)-connected n-vertex tournament T and given 2t distinct vertices x(1), ... , x(t), y(1), ... , y(t) of T, we can find t vertex disjoint paths P-1, ... , P-t such that each path P-i connecting x(i) and y(i) has the prescribed length, provided that the prescribed lengths are Omega(n). For both results, the condition of connectivity being linear in t is best possible, and the condition of prescribed sizes being Omega(n) is also best possible. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.title | On 1-factors with prescribed lengths in tournaments | - |
dc.type | Article | - |
dc.identifier.wosid | 000508288900002 | - |
dc.identifier.scopusid | 2-s2.0-85068218658 | - |
dc.type.rims | ART | - |
dc.citation.volume | 141 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 31 | - |
dc.citation.endingpage | 71 | - |
dc.citation.publicationname | JOURNAL OF COMBINATORIAL THEORY SERIES B | - |
dc.identifier.doi | 10.1016/j.jctb.2019.06.003 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Tournament | - |
dc.subject.keywordAuthor | Connectivity | - |
dc.subject.keywordAuthor | 1-factor | - |
dc.subject.keywordAuthor | Cycle | - |
dc.subject.keywordAuthor | Graph partition | - |
dc.subject.keywordPlus | COMPLEMENTARY CYCLES | - |
dc.subject.keywordPlus | VERTICES | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | CONNECTIVITY | - |
dc.subject.keywordPlus | CONJECTURE | - |
dc.subject.keywordPlus | PARTITION | - |
dc.subject.keywordPlus | PROOF | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.