Page 1

Displaying 1 – 17 of 17

Showing per page

Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

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

Commentationes Mathematicae Universitatis Carolinae

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.

Note on the weight of paths in plane triangulations of minimum degree 4 and 5

Tomás Madaras (2000)

Discussiones Mathematicae Graph Theory

The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.

Currently displaying 1 – 17 of 17

Page 1