Perfect Path Double Covers of Graphs
| Speaker: | Cheolwon Heo |
|---|---|
| Affiliation: | Combinatorics and Optimization, University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5168 |
Abstract:
A
cycle
double
cover
(CDC)
of
a
graph
G
is
a
collection
C
of
cycles
of
G
such
that
each
edge
of
G
lies
in
exactly
two
cycles
of
C.
There
is
a
well
known
conjecture
of
Seymour
that
every
bridgeless
graph
admits
a
CDC.
Bondy
proposed
a
strong
version
of
this
conjecture,
namely
that
every
bridgeless
graph
admits
a
“small”
cycle
double
cover
(SCDC).
A
perfect
path
double
cover
(PPDC)
of
a
graph
G
is
a
collection
P
of
paths
of
G
such
that
each
edge
of
G
lies
in
exactly
two
paths
of
P
and
each
vertex
of
G
occurs
exactly
twice
as
an
end
of
a
path
of
P.
Bondy
conjectured
that
every
simple
graph
admits
a
PPDC.
He
shows
that
these
two
conjectures
are
related
by
proving
that
for
trigraphs
the
SCDC
and
PPDC
conjecture
are
equivalent.
In
1990,
Li
proved
the
PPDC
conjecture.
I
will
also
introduce
generalizations
of
the
PPDC
conjecture
and
discuss
related
problems.