Přejít k obsahu


Hamiltonian Cycles in the Square of a Graph

Citace: [] EKSTEIN, J. Hamiltonian Cycles in the Square of a Graph. In The 2nd Young Researchers Conference on Applied Sciences. V Plzni: Západočeská univerzita, 2008. s. 7-12. ISBN: 978-80-7043-698-1
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Hamiltonian Cycles in the Square of a Graph
Rok vydání: 2008
Místo konání: V Plzni
Název zdroje: Západočeská univerzita
Autoři: Jan Ekstein
Abstrakt CZ: Ukážeme, že za určitých podmínek graf vzniklý ztotožněním vrcholu ve dvou grafech s hamiltonovskou mocninou je rovněž hamiltonovský. Uvedeme nutné a postačující podmínky hamiltonovskosti druhé mocniny souvislého grafu takového, že každý vrchol stupně alespoň tři v blokovém grafu odpovídá artikulaci a každé dva takové vrcholy jsou ve vzdálenosti alespoň čtyři.
Abstrakt EN: We show that under certain conditions the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. Using this result, we prove necessary and sufficient conditions for hamiltonicity of the square of a connected graph such that every vertex of degree at least three in a block graph corresponds to a cut vertex and any two these vertices are at distance at least four.
Klíčová slova

Zpět

Patička