| Název: | Znovuobnovení hamiltonovského tématu v druhé mocnině bloku: případ DT-grafů Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs |
| Autoři: | Chia, Gek L. Ekstein, Jan Fleischner, Herbert |
| Citace zdrojového dokumentu: | CHIA, G. L., EKSTEIN, J., FLEISCHNER, H. Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs. Journal of Combinatorics, 2018, roč. 9, č. 1, s. 119-161. ISSN 2156-3527. |
| Datum vydání: | 2018 |
| Nakladatel: | International Press |
| Typ dokumentu: | článek article |
| URI: | http://hdl.handle.net/11025/29318 |
| ISSN: | 2156-3527 |
| Klíčová slova: | Hamiltonovské kružnice a cesty;druhá mocnina bloku |
| Klíčová slova v dalším jazyce: | Hamiltonian cycles and paths;square of a block |
| Abstrakt: | Druhá mocnina grafu G, značí se G^2, je graf, který získáme z G spojením hranou každé dva nesousední vrcholy se společným sousedem. Graf G má F_k vlastnost, jestliže pro každou množinu k různých vrcholů {x_1,x_2,...,x_k} v G existuje hamiltonovská cesta z x_1 do x_2 v G^2 obsahující k-2 různých hran G tvaru x_i z_i, i=3,...,k. V [7] bylo dokázáno, že každý 2-souvislý graf má F_3 vlastnost. V první části této práce rozšíříme tento výsledek dokázáním, že každý 2-souvislý DT-graf má F_4 vlastnost (Věta 2), a ukážeme v druhé části, že toto rozšíření platí i pro libovolné 2-souvislé grafy a neexistují 2-souvislé grafy s F_k vlastností pro každé přirozené k>=5. Celkově je zodpovězen problém zmíněný v [4]. |
| Abstrakt v dalším jazyce: | The square of a graph G, denoted G^2, is the graph obtained from G by joining by an edge any two nonadjacent vertices which have a common neighbor. A graph G is said to have F_k property if for any set of k distinct vertices {x_1,x_2,...,x_k} in G, there is a hamiltonian path from x_1 to x_2 in G^2 containig k-2 distinct edges of G of the form x_i z_i, i=3,...,k. In [7], it was proved that every 2-connected graph has the F_3 property. In the first part of this work, we extend this result by proving that every 2-connected DT-graph has the F_4 property (Theorem 2) and will show in the second part that this generalization holds for arbitrary 2-connected graphs, and that there exist 2-connected graphs which do not have the F_k property for any natural number k>=5. Altogether, this answers the second problem raised in [4] in the affirmative. |
| Práva: | Plný text není přístupný. © International Press |
| Vyskytuje se v kolekcích: | Články / Articles (KMA) OBD |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| JOC 09 01 A07.pdf | 449,8 kB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/29318Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.