MathDB

A boa of size

k

is a graph with

k+1

vertices

\{0,1,\dots,k-1,k\}

and edges only between the vertices

i

and

i+1

for

0\leq i < k.

The boa is place in a graph

G

through a injection of graphs. (This is an injective function form the vertices of the boa to the vertices of the graph in such a way that if there is an edge between the vertices

x

and

y

in the boa then there must be an edge between

f(x)

and

f(y)

G

). The Boa can move in the graph

G

using to type of movement each time. If the boa is initially on the vertices

f(0),f(1),\dots,f(k)

then it moves in one of the following ways:
(i) It choose

v

a neighbor of

f(k)

such that

v\not\in\{f(0),f(1),\dots,f(k-1)\}

and the boa now moves to

f(0),f(1),\dots,f(k)

with

f'(k)=v

and

f'(i) = f(i+1)

for

0 \leq i < k,

or
(ii) It choose

v

a neighbor of

f(0)

such that

v\not\in\{f(1),f(2),\dots,f(k)\}

and the boa now moves to

f(0),f(1),\dots,f(k)

with

f'(0)=v

and

f'(i) = f'(i-1)

for

0 < i \leq k.

Prove that if

G

is a connected graph with diameter

d

, then it is possible to put a size

\lceil d/2 \rceil

boa in

G

such that the boa can reach any vertex of

G

Problem Statement