Přejít k obsahu


{4,5} Is Not Coverable: A Counterexample to a Conjecture of Kaiser and Škrekovski

Citace: ČADA, R., CHIBA, S., OZEKI, K., VRÁNA, P., YOSHIMOTO, K. {4,5} Is Not Coverable: A Counterexample to a Conjecture of Kaiser and Škrekovski. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, roč. 27, č. 1, s. 141-144. ISSN: 0895-4801
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: {4,5} Is Not Coverable: A Counterexample to a Conjecture of Kaiser and Škrekovski
Rok vydání: 2013
Autoři: Doc. Ing. Roman Čada Ph.D. , Shuya Chiba , Kenta Ozeki , Mgr. Petr Vrána Ph.D. , Kiyoshi Yoshimoto
Abstrakt CZ: Pokud A je podmnožina kladných celých čísel, řekneme, že graf G je A-pokrytelný, pokud má G sudý podgraf, který protíná všechny hranové řezy o velikosti, která je v A. Množina A se nazývá pokrytelná, pokud jsou všechny grafy A-pokrytelné. Jako možný přístup k hypotéze o dominujících kružnicích vyslovili Kaiser a Škrekovski hypotézu, že množina N+3={4,5,6,...} je pokrytelná. V článku je tato hypotéza vyvrácená ukázáním nekonečné množiny grafů, které nejsou {4,5}-pokrytelné.
Abstrakt EN: For a subset A of the set of positive integers, a graph G is called A-coverable if G has a cycle (a subgraph in which all vertices have even degree) which intersects all edge-cuts T in G with |T| is in A, and A is said to be coverable if all graphs are A-coverable. As a possible approach to the dominating cycle conjecture, Kaiser and Škrekovski conjectured that N+3 is coverable, where N+3 = {4,5,6,...}. In this paper, we disprove Kaiser and Škrekovski's conjecture by showing that there exist infinitely many graphs which are not {4,5}-coverable. Read More: http://epubs.siam.org/doi/abs/10.1137/120877817
Klíčová slova

Zpět

Patička