Thursday, March 5, 2015 1:30 pm
-
1:30 pm
EST (GMT -05:00)
Cores of cubelike graphs
| Speaker: | David Roberson |
|---|---|
| Affiliation: | Nanyang Technological University |
| Room: | Mathematics 3 (M3) 2134 |
Abstract:
A
graph
is
said
to
be
cubelike
if
it
is
a
Cayley
graph
for
some
power
of
the
field
of
order
two.
The
core
of
a
graph
is
its
smallest
subgraph
to
which
it
admits
a
homomorphism.
In
this
talk
we
consider
the
following
open
question:
Is
the
core
of
a
cubelike
graph
cubelike?
We
will
discuss
the
previously
known
results
on
this
problem
before
proving
the
following:
Theorem:
If
X
is
a
core
of
a
cubelike
graph
and
has
degree
k,
then
X
has
at
most
2^(k-1)
vertices
or
is
K_2.
Furthermore,
if
k
is
at
least
2
and
the
above
bound
is
met,
then
k
is
odd
and
X
is
the
folded
cube
of
order
k.
This
result
is
as
expected
if
the
answer
to
the
above
question
is
"yes",
and
thus
it
provides
some
evidence
that
this
is
in
fact
the
case.