F. Göring, J. Harant: Prescribed edges and forbidden edges for a cycle in a planar graph

Author(s):

F. Göring
J. Harant

Title:

F. Göring, J. Harant: Prescribed edges and forbidden edges for a cycle in a planar graph

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 17, 2010

Mathematics Subject Classification:

05C38	[]
05C40	[]
05C45	[]

Abstract:

In 19656, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. J. Harant and S. Senitsch (Disc. Math. 309(2009)4949-4951) even proved that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph G[X] of G induced by X if |X| >= 3 and if X is 4-connected in G. If X=V(G) then Sanders'result follows. Here we consider the case that X is 5-connected in G and that there are prescribed edges and forbidden edges of G|X| for a cycle through X.

Keywords:

Planar graph, Cycle

Language:

English

Publication time:

2010