Přejít k obsahu


Hamiltonian Cycles in the Square of a Graph with Block Graph Homeomorphic to a Star

Citace: [] EKSTEIN, J. Hamiltonian Cycles in the Square of a Graph with Block Graph Homeomorphic to a Star. In Graphs 2007. Ostrava: VŠB - Technickal University, 2007. s. 8-8. ISBN: 978-80-248-1445-2
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Hamiltonian Cycles in the Square of a Graph with Block Graph Homeomorphic to a Star
Rok vydání: 2007
Místo konání: Ostrava
Název zdroje: VŠB - Technickal University
Autoři: Jan Ekstein
Abstrakt CZ: Nechť G je prostý neorientovaný graf. Druhá mocnina grafu G je graf G{2} se stejnou množinou vrcholů jako G, v kterém dva vrcholy jsou spojené hranou, pokud jejich vzdálenost v G je nejvýše 2. Ukážeme, že za určitých podmínek druhá mocnina grafu získaného ztotožněním vrcholu v dvou grafech s hamiltonovskou druhou mocninou je rovněž hamiltonovská. Uvedeme (polynomiálně ověřitelné) nutné a postačující podmínky hamiltonovskosti druhé mocniny souvislého grafu, jehož blokový graf je homeomorfní s hvězdou, v kterém střed hvězdy odpovídá artikulaci, a postačující podmínky hamiltonovskosti druhé mocniny souvislého grafu, jehož blokový graf je homeomorfní s hvězdou, v kterém střed hvězdy odpovídá bloku.
Abstrakt EN: Let G be a simple undirected graph. The square of G is the graph G{2} with the same vertex set as G, in which two vertices are adjacent if and only if their distance in G is at most 2. We show that under certain condition the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. We present (polynomially verifiable) necessary and sufficient conditions for hamiltonicity of the square of a connected graph whose block graph is homeomorphic to a star in which the center corresponds to a cut vertex, and sufficient conditions for hamiltonicity of the square of a connected graph whose block graph is homeomorphic to a star in which the center corresponds to a block.
Klíčová slova

Zpět

Patička