SharedDefinitions_and_Theorems.texOpen in CoCalc

% set font encoding for PDFLaTeX, XeLaTeX, or LuaTeX



\title{GBP---Hamiltonicity---Summer 2018}

% Enable SageTeX to run SageMath code right inside this LaTeX file.
% \usepackage{sagetex}



{\bf A note to the reader: all graphs here are simple, connected, and of order at least three.}

\section*{Some True Conjectures}

\begin{obs} If $G$ is a complete graph, then $G$ is Hamiltonian.\end{obs}

\begin{lem} If $G$ is a bipartite $k$-regular graph, with $k>0$ and bipartition $(X,Y)$, then $|X|=|Y|$.\end{lem}
This is immediate by double counting; $k|X|=\sum_{x\in X}d(x)=e(G)=\sum_{y\in Y}d(y)=k|Y|$.

\begin{lem} If there is a graph which is $(n,k,\lambda,\mu)$-strongly-regular, then $(n-k-1)\mu=k(k-\lambda-1)$.

We partition the graph into three sets. Let $x$ be an arbitrary vertex; we think of this as the root of our partition; say $P_0=\{x\}$. Since $G$ is $k$-regular, we think of its $k$ neighbors as being in the second set; formally, take $P_1=\{y:y\in N(x)\}$. All other nodes form the third set; take $P_2=\{y:y\not\in N(x)\wedge y\neq x\}$.

Since the vertices of $P_1$ are adjacent to $x$, they have $\lambda$ neighbors in common with the $x$; these vertices must also lie in $P_1$. Since our graph is $k$=regular, there are $(k-\lambda -1)$ edges remaining from each $P_1$ vertex to $P_2$. Thus we have $e(P_1,P_2)=k (k-\lambda -1).$

Since the vertices in $P_2$ are not adjacent to $x$, they must have $\mu$ common neighbors with $x$; these vertices are in $P_1$. Since $|P_2|=(n-k-1)$, and each vertex of $P_2$ is connected to $\mu$ nodes of $P_1$, we have $e(P_1,P_2)=(n-k-1)\mu$.  Comparing with our earlier count of $e(P_1,P_2)$, we see that $(n-k-1)\mu=k(k-\lambda-1)$.

\begin{thm} If $G$ is a bipartite, connected, $(n,k,\lambda,\mu)$-strongly-regular graph, then $G$ is a complete balanced bipartite graph.\end{thm}
\begin{proof}Assume that $G$ is as stated, with bipartition $(X,Y)$.\\

First, notice that if $\lambda>0$, then $G$ contains a triangle; this is impossible, if $G$ is bipartite, and so we may assume that $\lambda=0$.\\

Now, assume that $\mu=1$; this implies that $G$ is a Moore graphs with girth five; this is impossible as $G$ is purported to be bipartite.\\

Next, suppose that $\mu=0$.  A quick counting argument shows that always $(n-k-1)\mu=k(k-\lambda-1)$. Simplifying in the case that $\mu=0$ and $\nu=0$, we see that $k-1=0$, and so $k=2$.  Thus $G$ is an even cycle, which is never strongly regular with the given parameters.\\

Finally, suppose that $\mu\ge 2$, and consider $x\in X$ and $y\in Y$ such that $xy\not\in E(G)$.  Then by definition these vertices have $\mu\ge 2$ neighbors in common; this is impossible as $G$ is bipartite and $x,y$ lie in different parts.  $G$ can have no such non-edge, and so it is complete.  By our lemma, it is also balanced since it is regular.

\begin{obs} If $G$ is a line graph whose complement is chordal and which has radius equal to diameter, then $G$ is Hamiltonian.\end{obs}
``is-line-graph implies claw-free;
is-complement-of-chordal implies P6-free;
has-radius-equal-diameter implies 2-connected;
And every 2-connected (P6 ,claw )-free graph is hamiltonian''

\begin{obs} If $G$ is a two connected outerplanar graph, then it is Hamiltonian.\end{obs}
This is trivial; the boundary of the infinite face must thus be a cycle, and as every vertex is on this face it forms a spanning cycle.

\begin{obs} If $G$ is a Gallai tree and is two connected, then $G$ is Hamiltonian.\end{obs}
Again, this is immediate -- any two bricks in a Gallai tree are separated by a cut vertex, so a two connected Gallai tree must be just a single brick.  This is either an odd cycle or a complete graph, so it is Hamiltonian.

\begin{lem} If $G$ is a nontrivial cartesian product and outerplanar, then it is Hamiltonian.\end{lem}
This relies on the fact that a graph is outerplanar if and only if it contains no $\{K_{2,3},K_4\}$-minor.

\begin{obs} If $G$ is a graph with its diameter equal to its radius, and $G$ is circular planar, then it is Hamiltonian.\end{obs}
This is again trivial; if $G$ contains a cut vertex or cut edge, and is outerplanar, then it has its diameter larger than its radius.

\begin{obs} If $G$ is a bipartite line graph, and it has diameter equal to radius, then it is Hamiltonian.\end{obs}
Recall that a graph is a line graph if and only if it can be partitioned into edge disjoint cliques such that every vertex lies in exactly two cliques.  Since $G$ is bipartite, it is triangle free, so such cliques are singletons or edges.  Every vertex is in exactly two such cliques, and so every vertex has degree at most two.  Since $G$ is connected, our graph is either a path or a cycle. Paths consisting of more than a single edge do not have radius equal to diameter, so our graph is a spanning cycle.

\begin{lem} A graph is outerplanar if and only if it is $K_{2,3}$-minor
free and $K_4$-minor-free.\end{lem}

\begin{lem} $P_2 \Box P_k$ is Hamiltonian for $k \ge2$.\end{lem}

\begin{lem} Suppose a graph $H$ is connected, outerplanar, and Hamiltonian. Further suppose $H = H_1 \Box H_2$ where $H_1$ and $H_2$ are graphs on at least two vertices.\end{lem}

Since $H$ is connected, so are $H_1$ and $H_2$.

\begin{clm}  $H$ is $P_2 \Box P_m$\end{clm}

Suppose that $H_1$ has a cycle. Since $H_2$ has an edge, $H$ contains
$K_3 \Box P_2$ as a minor and thus it contains $K_{2,3}$ as a minor
(take the open neighborhood of any vertex to be the class of size 3),
a contradiction.

Thus, $H_1$ and $H_2$ are trees. If $H_1$ has a vertex of degree 3 or
more, then $H$ contains $K_{1,3} \Box P_2$ as a minor. Taking the
neighborhood of one of the vertices of degree 3 in $K_{1,3}$ and the
other copy of $K_{1,3}$ as the class of size 2, we see that $H$ has
$K_{2,3}$ as a minor, a contradiction.

Thus, $H_1$ and $H_2$ are paths. Suppose that both have three or more
vertices. Thus $H$ contains $H_1 \Box H_2$ as a minor. Taking the
neighbors of a vertex of degree 3 as the class of size 3 shows that
$H$ contains a $K_{2,3}$-minor, a contradiction.

Thus at least one of $H_1$ and $H_2$ has exactly two vertices and the
proof is complete.\end{proof}

\section*{Planar Transitive Graphs are Hamiltonian}

\begin{defi} A graph automorphism is an isomorphism between the graph and itself.  That is, it is a map $\phi:V(G)\to V(G)$ such that $xy\in E(G)$ iff $\phi(x)\phi(y)\in E(G)$. A graph $G$ is {\em vertex transitive} if for every pair of vertices $u,v\in V(G)$, there is a graph automorphism $\phi$ with $\phi(u)=\phi(v)$.

\begin{obs} Every vertex transitive graph is $d$-regular for some $k\in\mathbb{N}$.\end{obs}

\begin{thm}{\cite{Mad70}}\label{mader} If $G$ is a $d$-regular vertex transitive graph with connectivity $k$, then $\frac{2(d+1)}{3}\le k$.\end{thm}

\begin{thm}{\cite{tutte}}\label{4con} Every $4$-connected planar graph is Hamiltonian.\end{thm}

\begin{thm}{\cite{zelinka3}}\label{zel} The only $3$-regular vertex transitive simple planar graphs are the tetrahedron, the dodecahedron, the $n$-sided prisms (for $n\ge 3$), the tricone graph, the truncated cube,  truncated octahedron, trunctated dodecahedron, truncated icosahedron (bucky ball), and the Great Rhombicosidodecahedral Graph.\end{thm}

We prove the following theorem.
\begin{thm} Every vertex transitive planar graph is Hamiltonian.\end{thm}

By Theorem \ref{4con}, it is enough for us to consider graphs with connectivity at most three. By Theorem \ref{mader}, such graphs are regular of degree at most $7/2$; that is, they either have all vertices of degree two or of degree three. Since a two-regular connected graph is a cycle (and thus Hamiltonian), we focus only on the three regular case.  But, these graphs are characterized by Theorem \ref{zel}.  The only infinite family of graphs here are the prisms (which are trivially Hamiltonian -- just walk around all but a single edge on one of the end polygons, across the adjacent face, around the opposing end, and back along the same face).  The other graphs are easily tested to be Hamiltonian in {\tt Sage}.

\bibitem[Mad70]{Mad70} W. Mader,{\em Uber den Zusammenhang symmetrischer Graphen}, Arch. Math.
{\bf 21} (1970) pp. 331--336.
\bibitem[Tut56]{tutte} T. Tutte, {\em A Theorem on Planar Graphs}, Trans. Amer. Math. Soc., {\bf 82} (1956), pp. 99--11.
\bibitem[Zel77]{zelinka3} B. Zelinka, {\em Finite Planar Vertex-Transitive Graphs of the Regularity Degree Three}, \v{C}asopis pro p\v{e}stov\'{a}ni matematiky, {\bf 102} (1977), issue 1, pp. 1--9.
\bibitem[Zel75]{zelinka45} B. Zelinka, {\em Finite Vertex-Transitive Planar Graphs of the Regularity Degree Four or Five.} Matematicka \v{C}asopis {\bf 25} (1975), issue 3, pp. 271--280.