Přejít k obsahu


Hamiltonian Cycles in the Square of a Graph

Citace: [] EKSTEIN, J. Hamiltonian Cycles in the Square of a Graph. ELECTRONIC JOURNAL OF COMBINATORICS, 2011, roč. 18, č. 1, s. 1-13. ISSN: 1077-8926
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Hamiltonian Cycles in the Square of a Graph
Rok vydání: 2011
Autoři: RNDr. Jan Ekstein
Abstrakt CZ: Ukážeme, že za jistých podmínek druhá mocnina grafu vzniklého ztotožněním vrcholu ve dvou grafech s hamiltonovskou druhou mocninou je rovněž hamiltonovská. S využitím tohoto výsledku dokážeme nutné a postačující podmínky hamiltonicity druhé mocniny souvislého grafu, jehož každý vrchol stupně alespoň tři v jeho blokovém grafu odpovídá artikulaci a každé takové dva 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