Decycling of Fibonacci Cubes

Yubo Zou

ABSTRACT: The decycling number &nabla(G) of a graph G is the smallest number of vertices that can be deleted from G so that the resultant graph contains no cycle. A Fibonacci string of order n is a binary string of length n with no two consecutive ones. The Fibonacci cube of order n is the graph whose vertices are the Fibonacci strings of length n such that two vertices are adjacent if they differ in just one position. The family of Fibonacci cubes has applications in interconnection topologies. In this talk, we will study the decycling number of the Fibonacci cubes. Lower and upper bounds of the decycling number for the Fibonacci cubes will be presented, as well as the exact value of the decycling number for n<8.