**
Title:**
A
closure
lemma
for
tough
graphs
and
Hamiltonian
ideals

Speaker:
| Chinh T. Hoang |

Affiliation:
| Wilfrid Laurier University |

Location:
| MC 5417 |

**
Abstract:**
The
closure
of
a
graph
$G$
is
the
graph
$G^*$
obtained
from
$G$
by
repeatedly
adding
edges
between
pairs
of
non-adjacent
vertices
whose
degree
sum
is
at
least
$n$,
where
$n$
is
the
number
of
vertices
of
$G$.
The
well-known
Closure
Lemma
proved
by
Bondy
and
Chv\'atal
states
that
a
graph
$G$
is
Hamiltonian
if
and
only
if
its
closure
$G^*$
is.
This
lemma
can
be
used
to
prove
several
classical
results
in
Hamiltonian
graph
theory.
We
prove
a
version
of
the
Closure
Lemma
for
tough
graphs.
A
graph
$G$
is
$t$-tough
if
for
any
set
$S$
of
vertices
of
$G$,
the
number
of
components
of
$G-S$
is
at
most
$t|S|$.
A
Hamiltonian
graph
must
necessarily
be
1-tough.
Conversely,
Chv\'atal
conjectured
that
there
exists
a
constant
$t$
such
that
every
$t$-tough
graph
is
Hamiltonian.
The
$t$-closure
of
a
graph
$G$
is
the
graph
$G^{t*}$
obtained
from
$G$
by
repeatedly
adding
edges
between
pairs
of
non-adjacent
vertices
whose
degree
sum
is
at
least
$n-t$.
We
prove
that,
for
$t
\geq
2$,
a
$\frac{3t-1}{2}$-tough
graph
$G$
is
Hamiltonian
if
and
only
if
its
$t$-closure
$G^{t*}$
is.
Ho\`ang
conjectured
the
following:
Let
$G$
be
a
graph
with
degree
sequence
$d_1
\leq
d_2
\leq
\dots
\leq
d_n$;
then
$G$
is
Hamiltonian
if
$G$
is
$t$-tough
and,
$\forall
i
<
\frac{n}{2}$,
if
$d_i
\leq
i$
then
$d_{n-i+t}
\geq
n-i$.
This
conjecture
is
analogous
to
the
well
known
theorem
of
Chv\'atal
on
Hamiltonian
ideals.
Ho\`ang
proved
the
conjecture
for
$t
\leq
3$.
Using
the
closure
lemma
for
tough
graphs,
we
prove
the
conjecture
for
$t
=
4$.
This
is
joint
work
with
Cl\'eoph\'ee
Robin.