% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{epsf,tikz}
\begin{document}

\setcounter{page}{79}

\newcommand{\satz}[1]{Theorem \ref{#1}}
\newcommand{\lemma}[1]{Lemma \ref{#1}}
\newcommand{\NN}{{\mathbf N}}
\setlength{\unitlength}{1cm}
\newtheorem{Satz}{Theorem}
\newtheorem{Lemma}{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{Bemer}{Remark}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{On Hamiltonian cycles through prescribed edges of a planar graph}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Jochen Harant}

\address{Department of Mathematics, Technical University of Ilmenau,\\
D-98684 Ilmenau, Germany}

\begin{keyword}
planar graph \sep hamiltonian cycle \sep prescribed edges
\end{keyword}

\end{frontmatter}

% main text

\noindent \noindent We use \cite{Diestel} for terminology and
notation not defined here and consider finite simple graphs only.\\
The first major result on the existence of hamiltonian cycles in
graphs embeddable in surfaces was by H. Whitney \cite{Whitney} in
1931, who proved that $4$-connected maximal planar graphs are
hamiltonian. In 1956, W.T. Tutte \cite{Tutte,Tutte1} generalized
Whitney's result from maximal planar graphs to arbitrary
$4$-connected planar graphs. Actually, Tutte proved that a
$4$-connected planar graph $G$ has a hamiltonian cycle through any
two edges of a given face of $G$. Moreover, in
\cite{Sanders,ThomasYu} it is proved that a $4$-connected planar
graph $G$ has a hamiltonian cycle through any three edges of a given
face of $G$ or that face is a $3$-gon.\\
Improving a result of C. Thomassen \cite{Thomassen}, in 1997, D.P.
Sanders \cite{Sanders} proved the following:
\begin{Satz}\label{Sanders}
(\cite{Sanders}) Every $4$-connected planar graph on at least three
vertices has a hamiltonian cycle through any two of its edges.
\end{Satz}



 In \cite{HarantSenitsch} the connectivity of a subset $X$
of the vertex set of a graph $G$ is defined as follows. Let $G$ be a
graph, $X\subseteq V(G)$, and $G[X]$ be the subgraph of $G$ induced
by $X$. A set $V\subset V(G)$ {\em splits} $X$ if the graph $G-V$
obtained from $G$ by removing $V$ contains at least two components
each containing a vertex of $X$. Let $\kappa (X)$ be infinity if
$G[X]$ is complete, or the minimum cardinality of a set $V\subset
V(G)$ splitting $X$. Let us remark that $G$ is $k$-connected if and
only if $\kappa (V(G))\ge k$.

Theorem \ref{local} is a local version of \satz{Sanders} and in case
$X=V(G)$, Theorem \ref{Sanders} follows from Theorem \ref{local}. It
is proven in \cite{HarantSenitsch}.
\begin{Satz}\label{local}
(\cite{HarantSenitsch}) If $G$ is a planar graph, $X\subseteq V(G)$,
$|X|\ge 3$, $\kappa (X)\ge 4$, $E\subset E(G[X])$, and $|E|\le 2$,
then $G$  contains a cycle $C$ with $X\subseteq V(C)$ and $E\subset
E(C)$.
\end{Satz}

The following theorem is proven in \cite{Gerlach} and, unlike Theorem \ref{local}, it is
appropriable  if $|E|\ge 3$.
\begin{Satz}\label{local2}
(\cite{Gerlach}, Theorem 6) If $G$ is a graph, $X\subseteq V(G)$,
$E\neq \emptyset $ is a set of independent edges of $G[X]$, $|X|\ge
2|E|+1$, and $\kappa (X)\ge |X|-|E|$, then $G$ contains a cycle $C$
with $X\subseteq V(C)$ and $E\subset E(C)$.
\end{Satz}
Note that Theorem \ref{local2} holds for arbitrary graphs.  Obviously
$|X|\ge 2|E|$ since $E$ is a set of independent edges of $G[X]$.\footnote{ The
inequality $|X|\ge 2|E|+1$ is needed in the proof of Theorem
\ref{local2} because of technical reasons. Probably Theorem
\ref{local2} also holds in case $|X|\ge 2|E|$. If in Theorem
\ref{local2}, additionally, $G$ is assumed to be planar, then it
remains an open problem whether the inequality $\kappa (X)\ge |X|-|E|$ can be
weakened.} If $X=V(G)$, $|X|-|E|\ge 6$, and $G$ is planar then Theorem \ref{local2}
cannot be used  since a planar graph is at most
$5$-connected.

We call a maximal planar graph $G$ a plane triangulation if $G$ is
embedded into the plane. In \cite{BH} it was shown that there are
$4$-connected plane triangulations containing seven faces of arbitrary distance apart
such that each hamiltonian cycle of that graph misses at least one
of these faces, i.e. seven edges cannot be guaranteed to belong to a
hamiltonian cycle of a $4$-connected planar graph even if their
pairwise distance is large.  Theorem \ref{Sanders}
is best possible in the sense that even three prescribed edges need not belong to
a hamiltonian cycle of a $4$-connected maximal planar graph.
Given two edges $xy$ and $uv$ of a graph $G$, the number of edges of
a shortest path in $G$ connecting a vertex of $\{x,y\}$ and a vertex
of $\{u,v\}$ is called the {\em distance } of $xy$ and $uv$.\\
\begin{Satz}\label{Satz1}
(\cite{GoeringHarant})
There is a $4$-connected plane triangulation
$G$ containing $E \subseteq E(G)$ with $3|E|=|E(G)|$ such that each
hamiltonian cycle of $G$ contains exactly two edges of $E$.
Moreover, for given integer $k\ge 1$, $G$ and $E$ can be chosen such that $E$
contains three edges of pairwise distance at least $k$.
\end{Satz}

The situation changes in comparison with Theorem \ref{Satz1}, if the
connectivity of $G$ is increased and the pairwise distance of the
edges in the set $E$ is at least three. In this case it is even
possible to forbid edges of $E$ to belong to a hamiltonian cycle as
described in the following Theorem \ref{Satz2}. A proof is given in
\cite{BHT}.

\begin{Satz}\label{Satz2}
(\cite{BHT}) Let $G$ be a $5$-connected plane triangulation and $E$
be a set of edges of $G$ such that the distance between any two
edges of $E$ is at
least three. Furthermore, let $E=E_1\cup E_2$ with $E_1\cap E_2=\emptyset $.
Then $G$ has a hamiltonian cycle $C$ with $E_1\subset E(C)$ and
$E_2\cap E(C)=\emptyset $.
\end{Satz}

Theorem \ref{Satz2} does not hold if the
$5$-connected plane graph $G$ is not a triangulation. Moreover, the existence of a cycle satisfying the assertion of Theorem \ref{Satz2}
cannot be guaranteed in
the case $|E|\ge 5$ and $E_2=\emptyset $, because
for each  integer $k$ there is a $5$-connected plane graph $G$
containing a set $E\subset E(G)$ with $|E|=5$ such that any two
edges of $E$ have distance at least $k$ and there is no cycle of $G$
containing $E$. \\ \\
For three edges of a $5$-connected plane triangulation the distance
condition in \satz{Satz2} can be omitted as follows.
\begin{Satz}\label{Satz3}
(\cite{GoeringHarant})
Let $G$ be a $5$-connected plane triangulation and $E$ be a set of
three edges of $G$ such that $E$ does not form a facial cycle and
there is no vertex incident with all edges of $E$.
Then $G$ has a hamiltonian cycle containing $E$.
\end{Satz}

Considering $5$-connected maximal planar graphs, the following
theorem is an analogue to \satz{Satz1}.

\begin{Satz} \label{Satz4} 
(\cite{GoeringHarant})
Let $G$ be a $5$-connected plane triangulation containing an
independent set $V$ of vertices such that each face
of $G$ is incident with exactly one vertex of $V$ and $H=G-V$ is $3$-regular.
Then each hamiltonian cycle of $G$ contains exactly $\frac{1}{3}|E(H)|-2=\frac{1}{3}(|V(G)|-8)$
edges of $H$.
\end{Satz}

Let $e_k$ be the smallest integer $l$ such that there is a
$5$-connected plane triangulation $G$ containing $l$ edges of
pairwise distance at least $k$ such that there is no hamiltonian
cycle of $G$ containing all these $l$ edges. If $e_k$ does not exist then we write $e_k=\infty $.\\ \\
Theorem \ref{Satz2} implies that $e_k=\infty$ if $k\ge 3$.

\begin{Satz}\label{Satz5}
(\cite{GoeringHarant})
For $e_1$ the inequalities $4\le e_1\le 9$ hold.\\
Moreover, there are infinitely many $5$-connected maximal planar
graphs $G$ containing a set $E$ of $\frac{1}{3}|E(G)|$ independent
edges such that each hamiltonian cycle of $G$ misses two edges of
$E$.
\end{Satz}

It remains open whether
$e_2$ is finite or not.

\label{}

% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\bibitem{BH} T. B\"ohme, J. Harant, On Hamiltonian Cycles in 4- and
5-connected Plane Triangulations, {\em Discrete Mathematics},
191(1998),25-30.
\bibitem{BHT} T. B\"ohme, J. Harant, M. Tk\'{a}\v{c}, On Certain
Hamiltonian Cycles in Planar Graphs, {\em Journal of Graph Theory}
32(1999)81-96.
\bibitem{Diestel} R. Diestel, Graph
Theory, Springer, Graduate Texts in Mathematics 173(2000).
\bibitem{Gerlach}
T. Gerlach, J. Harant, On a Cycle through a Specified Linear Forest
of a Graph, {\em Discrete Mathematics}, 307(2007)892-895.
\bibitem{GoeringHarant}F. G\"oring, J.Harant, Hamiltonian cycles through prescribed edges of  4-connected
maximal planar graphs, {\em Discrete Mathematics} 310(2010)
1491-1494.
\bibitem{HarantSenitsch} J. Harant, S.
Senitsch, A Generalization of Tutte's Theorem on Hamiltonian Cycles
in Planar Graphs, {\em Discrete Mathematics} 309(2009)4949-4951.
%\bibitem{KelmansLomonosov} A.K. Kelmans, M.V. Lomonosov, When $m$
%Vertices in a $k$-connected  Graph cannot be walked round along a
%Simple Cycle, {\em Discrete Mathematics} 38(1982)317-322.
\bibitem{Sanders}
D.P. Sanders, On Paths in Planar Graphs, {\em Journal of Graph
Theory} 24(1997)341-345.
\bibitem{ThomasYu} R. Thomas, X. Yu, Projective Planar Graphs are
Hamiltonian, {\em J. Combin. Theory} Ser. B 62(1994)114-132.
\bibitem{Thomassen} C.
Thomassen, A Theorem on Paths in Planar Graphs, {\em Journal of
Graph Theory} 7(1983)169-176.
\bibitem{Tutte}
W.T. Tutte, A Theorem on Planar Graphs, {\em Trans. Amer. Math.
Soc.} 82(1956)99-116.
\bibitem{Tutte1}
W.T. Tutte, Bridges and Hamiltonian Circuits in Planar Graphs, {\em
Aequationes Math.}15(1977)1-33.
\bibitem{Whitney}
 H. Whitney, A Theorem on Graphs, {\em Ann.Math. }32(1931)378-390.

\end{thebibliography}

\end{document}

