Displaying similar documents to “Note on Petri and Hamiltonian cycles in cubic polyhedral graphs.”

Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

Jaroslav Ivančo, Stanislav Jendroľ, Michal Tkáč (1994)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left and right edges at each successive vertex, i.ei̇t is also a Petrie cycle. The Petrie Hamiltonian cycle in an n -vertex plane cubic graph can be recognized by an O ( n ) -algorithm.

On Vertices Enforcing a Hamiltonian Cycle

Igor Fabrici, Erhard Hexel, Stanislav Jendrol’ (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.