Přejít k obsahu

Hamiltonian Cycles in the Square of a Graph

EKSTEIN, J. Hamiltonian Cycles in the Square of a Graph. 447 Altgeld Hall, Universityof Illinois, 2013.
Jazyk publikace: eng
Anglický název: Hamiltonian Cycles in the Square of a Graph
Rok vydání: 2013
Autoři: RNDr. Jan Ekstein Ph.D. ,
Abstrakt EN: Let G be a simple undirected graph. The square of G is the graph 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. A famous result of Fleischner states that the square of G of any 2-connected graph is hamiltonian. 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