Title: Theorems and Exchange Graph Algorithms concerning Paths, Cycles and Trees
| Speaker | Kathie Cameron |
| Affiliation: | Wilfred Laurier University |
| Room: | MC 6029 |
Abstract:
Carsten
Thomassen
and
I
proved
that
in
any
graph
G,
the
number
of
cycles
containing
a
specified
edge
as
well
as
all
the
odd-degree
vertices
is
odd
if
and
only
if
G
is
eulerian.
Where
all
vertices
have
even
degree
this
is
a
theorem
of
Sunichi
Toida
and
where
all
vertices
have
odd
degree
it
is
Andrew
Thomason's
generalization
of
Smith's
Theorem.
Kenneth
Berman
extended
Thomason’s
Theorem
to
trees:
he
used
a
counting
argument
to
prove
that
if
T
is
a
spanning
tree
of
a
graph
G
where
all
vertices
in
G-E(T)
have
odd
degree,
there
is
an
even
number
of
spanning
trees
of
G
with
the
same
degree
as
T
at
each
vertex.
I
give
a
common
generalization
of
these
results
to
a
parity
theorem
about
(not
necessarily
spanning)
trees.
Andrew
Thomason
proved
his
theorem
by
constructing
a
graph
X(G),
his
lollipop
graph,
in
which
the
odd-degree
vertices
correspond
precisely
to
the
things
he
wants
to
show
there
are
an
even
number
of,
namely
the
hamiltonian
cycles
in
G
containing
the
specified
edge.
Christos
Papadimitriou
calls
this
approach
the
polynomial
parity
argument
(PPA).
It
provides
an
algorithm
for
given
one
of
the
objects,
finding
another,
by
walking
in
X(G)
from
one
odd-degree
vertex
to
another.
I
have
extended
Thomason's
algorithm
to
one
which,
in
a
non-eulerian
graph,
finds
a
second
cycle
containing
a
specified
edge
and
all
the
odd-degree
vertices,
and
more
generally
finds
a
second
tree
with
certain
properties.
I
will
discuss
these
algorithms
and
some
other
parity
theorems.