The Fibonacci numbers of certain subgraphs of circulant graphs

The Fibonacci number ℱ(G)ℱ(G) of a graph GG with vertex set V(G)V(G), is the total number of independent vertex sets S⊂V(G)S⊂V(G); recall that a set S⊂V(G)S⊂V(G) is said to be independent whenever for every two different vertices u,v∈Su,v∈S there is no edge between them. In general, the problem to find the Fibonacci number of a graph is NP-complete. Prodinger and Tichy proved that the Fibonacci number of PnPn, the path of order nn is Fn+2Fn+2, the n+2n+2-Fibonacci number; and the Fibonacci number of CnCn, the cycle of order nn, is LnLn, the nn-Lucas number.A circulant graph Cn(m1,m2,…,mr)Cn(m1,m2,…,mr) is a graph of order nn with vertex set V={v1,v2,…,vn}V={v1,v2,…,vn} and edge set E={vivi+mj(modn):i∈{1,2,…,n},j∈{1,2,…,r}}, where r∈Z+r∈Z+. The values mjmj are the jump sizes. In this paper we only deal with the circulant graphs of order nn with rr consecutive jumps 1,2,…,r1,2,…,r. Cn(1,2,…,r)Cn(1,2,…,r) is denoted by Cn[r]Cn[r].We prove that the total number of independent vertex sets of the family of graphs Cn[r]Cn[r] for all n≥r+1n≥r+1, and for several subgraphs of this family is completely determined by some sequences which are constructed recursively like the Fibonacci and Lucas sequences, even more, these new sequences generalize the Fibonacci and Lucas sequences.