Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 77
1
\documentclass{amsart}
2
3
% set font encoding for PDFLaTeX, XeLaTeX, or LuaTeX
4
\usepackage{ifxetex,ifluatex}
5
\newif\ifxetexorluatex
6
\ifxetex
7
\xetexorluatextrue
8
\else
9
\ifluatex
10
\xetexorluatextrue
11
\else
12
\xetexorluatexfalse
13
\fi
14
\fi
15
16
\ifxetexorluatex
17
\usepackage{fontspec}
18
\else
19
\usepackage[T1]{fontenc}
20
\usepackage[utf8]{inputenc}
21
\usepackage{lmodern}
22
\fi
23
24
\usepackage{hyperref}
25
26
\title{GBP---Hamiltonicity---Summer 2018}
27
\author{GBP}
28
29
% Enable SageTeX to run SageMath code right inside this LaTeX file.
30
% http://mirrors.ctan.org/macros/latex/contrib/sagetex/sagetexpackage.pdf
31
% \usepackage{sagetex}
32
33
%\theoremstyle{plain}
34
\newtheorem{thm}{Theorem}
35
\newtheorem{prop}[thm]{Proposition}
36
\newtheorem{lem}[thm]{Lemma}
37
\newtheorem{conj}{Conjecture}
38
\newtheorem{cor}[thm]{Corollary}
39
\newtheorem{prob}[thm]{Problem}
40
\newtheorem{defi}[thm]{Definition}
41
\newtheorem{obs}{Observation}
42
\newtheorem{clm}{Claim}
43
\newtheorem{question}{Question}
44
45
46
47
\begin{document}
48
49
50
51
52
\maketitle
53
{\bf A note to the reader: all graphs here are simple, connected, and of order at least three.}
54
55
\section*{Some True Conjectures}
56
57
\begin{obs} If $G$ is a complete graph, then $G$ is Hamiltonian.\end{obs}
58
59
\begin{lem} If $G$ is a bipartite $k$-regular graph, with $k>0$ and bipartition $(X,Y)$, then $|X|=|Y|$.\end{lem}
60
This is immediate by double counting; $k|X|=\sum_{x\in X}d(x)=e(G)=\sum_{y\in Y}d(y)=k|Y|$.
61
62
63
\begin{lem} If there is a graph which is $(n,k,\lambda,\mu)$-strongly-regular, then $(n-k-1)\mu=k(k-\lambda-1)$.
64
\end{lem}
65
66
\begin{proof}
67
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\}$.
68
69
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).$
70
71
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)$.
72
\end{proof}
73
74
\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}
75
\begin{proof}Assume that $G$ is as stated, with bipartition $(X,Y)$.\\
76
77
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$.\\
78
79
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.\\
80
81
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.\\
82
83
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.
84
\end{proof}
85
86
\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}
87
``is-line-graph implies claw-free;
88
is-complement-of-chordal implies P6-free;
89
has-radius-equal-diameter implies 2-connected;
90
And every 2-connected (P6 ,claw )-free graph is hamiltonian''
91
92
\begin{obs} If $G$ is a two connected outerplanar graph, then it is Hamiltonian.\end{obs}
93
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.
94
95
\begin{obs} If $G$ is a Gallai tree and is two connected, then $G$ is Hamiltonian.\end{obs}
96
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.
97
98
\begin{lem} If $G$ is a nontrivial cartesian product and outerplanar, then it is Hamiltonian.\end{lem}
99
This relies on the fact that a graph is outerplanar if and only if it contains no $\{K_{2,3},K_4\}$-minor.
100
101
\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}
102
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.
103
104
\begin{obs} If $G$ is a bipartite line graph, and it has diameter equal to radius, then it is Hamiltonian.\end{obs}
105
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.
106
107
108
\begin{lem} A graph is outerplanar if and only if it is $K_{2,3}$-minor
109
free and $K_4$-minor-free.\end{lem}
110
111
\begin{lem} $P_2 \Box P_k$ is Hamiltonian for $k \ge2$.\end{lem}
112
113
\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}
114
115
\begin{proof}
116
Since $H$ is connected, so are $H_1$ and $H_2$.
117
118
119
\begin{clm} $H$ is $P_2 \Box P_m$\end{clm}
120
121
122
Suppose that $H_1$ has a cycle. Since $H_2$ has an edge, $H$ contains
123
$K_3 \Box P_2$ as a minor and thus it contains $K_{2,3}$ as a minor
124
(take the open neighborhood of any vertex to be the class of size 3),
125
a contradiction.
126
127
Thus, $H_1$ and $H_2$ are trees. If $H_1$ has a vertex of degree 3 or
128
more, then $H$ contains $K_{1,3} \Box P_2$ as a minor. Taking the
129
neighborhood of one of the vertices of degree 3 in $K_{1,3}$ and the
130
other copy of $K_{1,3}$ as the class of size 2, we see that $H$ has
131
$K_{2,3}$ as a minor, a contradiction.
132
133
Thus, $H_1$ and $H_2$ are paths. Suppose that both have three or more
134
vertices. Thus $H$ contains $H_1 \Box H_2$ as a minor. Taking the
135
neighbors of a vertex of degree 3 as the class of size 3 shows that
136
$H$ contains a $K_{2,3}$-minor, a contradiction.
137
138
Thus at least one of $H_1$ and $H_2$ has exactly two vertices and the
139
proof is complete.\end{proof}
140
141
\section*{Planar Transitive Graphs are Hamiltonian}
142
143
\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)$.
144
\end{defi}
145
146
\begin{obs} Every vertex transitive graph is $d$-regular for some $k\in\mathbb{N}$.\end{obs}
147
148
\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}
149
150
\begin{thm}{\cite{tutte}}\label{4con} Every $4$-connected planar graph is Hamiltonian.\end{thm}
151
152
\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}
153
154
We prove the following theorem.
155
\begin{thm} Every vertex transitive planar graph is Hamiltonian.\end{thm}
156
157
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}.
158
\begin{thebibliography}{9}
159
160
\bibitem[Mad70]{Mad70} W. Mader,{\em Uber den Zusammenhang symmetrischer Graphen}, Arch. Math.
161
{\bf 21} (1970) pp. 331--336.
162
\bibitem[Tut56]{tutte} T. Tutte, {\em A Theorem on Planar Graphs}, Trans. Amer. Math. Soc., {\bf 82} (1956), pp. 99--11.
163
\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.
164
\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.
165
166
167
\end{thebibliography}
168
169
\end{document}
170
171