Proofs of two conjectures on generalized Fibonacci cubes

Publication date 30 September 2015

Abstract: A binary string

f

is a factor of string

u

if

f

appears as a sequence of

| f |

consecutive bits of

u

, where

| f |

denotes the length of

f

. Generalized Fibonacci cube

Q_{d} (f)

is the graph obtained from the

d

-cube

Q_{d}

by removing all vertices that contain a given binary string

f

as a factor. A binary string

f

is called good if

Q_{d} (f)

is an isometric subgraph of

Q_{d}

for all

d g e q 1

, it is called bad otherwise. The index of a binary string

f

, denoted by

B (f)

, is the smallest integer

d

such that

Q_{d} (f)

is not an isometric subgraph of

Q_{d}

. Ili'{c}, Klavv{z}ar and Rho conjectured that

B (f) < 2 | f |

for any bad string

f

. They also conjectured that if

Q_{d} (f)

is an isometric subgraph of

Q_{d}

, then

Q_{d} (f f)

is an isometric subgraph of

Q_{d}

. We confirm the two conjectures by obtaining a basic result: if there exist

p

-critical words for

Q_{B (f)} (f)

, then

p

=2 or

p = 3

.

Recommendations

Cites work

Cited in

(36)

This page was built for publication: Proofs of two conjectures on generalized Fibonacci cubes