Mincuts in generalized Fibonacci graphs of degree 3

Abstract

We investigate the structure of mincuts in an n-vertex generalized Fibonacci graph of degree 3 and show that the number $|{\mathbf{CF}}_3\mathrm{(}\mathit{n}\mathrm{)}|$ of mincuts in this graph is equal to $|{\mathbf{CF}}_3\mathrm{(}\mathit{n}-1\mathrm{)}|+|{\mathbf{CF}}_3\mathrm{(}\mathit{n}-2\mathrm{)}|+|{\mathbf{CF}}_3\mathrm{(}\mathit{n}-3\mathrm{)}|-|{\mathbf{CF}}_3\mathrm{(}\mathit{n}-4\mathrm{)}|-|{\mathbf{CF}}_3\mathrm{(}\mathit{n}-5\mathrm{)}|+1$ .