Full metadata record
DC pole | Hodnota | Jazyk |
---|---|---|
dc.contributor.author | Chia, Gek L. | |
dc.contributor.author | Ekstein, Jan | |
dc.contributor.author | Fleischner, Herbert | |
dc.date.accessioned | 2018-02-21T11:35:30Z | - |
dc.date.available | 2018-02-21T11:35:30Z | - |
dc.date.issued | 2018 | |
dc.identifier.citation | 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. | en |
dc.identifier.issn | 2156-3527 | |
dc.identifier.uri | http://hdl.handle.net/11025/29318 | |
dc.description.abstract | 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]. | cs |
dc.format | 43 s. | cs |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | en |
dc.publisher | International Press | en |
dc.rights | Plný text není přístupný. | cs |
dc.rights | © International Press | en |
dc.subject | Hamiltonovské kružnice a cesty | cs |
dc.subject | druhá mocnina bloku | cs |
dc.title | Znovuobnovení hamiltonovského tématu v druhé mocnině bloku: případ DT-grafů | cs |
dc.title | Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs | en |
dc.type | článek | cs |
dc.type | article | en |
dc.rights.access | closedAccess | en |
dc.type.version | publishedVersion | en |
dc.description.abstract-translated | 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. | en |
dc.subject.translated | Hamiltonian cycles and paths | en |
dc.subject.translated | square of a block | en |
dc.identifier.doi | 10.4310/JOC.2018.v9.n1.a7 | |
dc.type.status | Peer-reviewed | en |
dc.identifier.obd | 43921236 | |
dc.project.ID | GBP202/12/G061/Centrum excelence - Institut teoretické informatiky (CE-ITI) | cs |
dc.project.ID | LO1506/PUNTIS - Podpora udržitelnosti centra NTIS - Nové technologie pro informační společnost | cs |
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/29318
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.