The adjacency graphs of some feedback shift registers

In this paper, we consider the adjacency graphs of some feedback shift registers (FSRs), namely, the FSRs with characteristic functions of the form (g=(x_0+x_1)*f). Firstly, we give some properties about these FSRs. We prove that these FSRs generate only prime cycles, and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. For example, it is shown that, when f contains an odd number of terms, the adjacency graph of ({mathrm {FSR}}((x_0+x_1)*f)) can be determined directly from the adjacency graph of ({mathrm {FSR}}(f)). Then, as an application of these results, we continue the work of Li et al. (IEEE Trans Inf Theory 60(5):3052–3061, 2014) to determine the adjacency graphs of ({mathrm {FSR}}((1+x)^4p(x))) and ({mathrm {FSR}}((1+x)^5p(x))), where p(x) is a primitive polynomial, and construct a large class of De Bruijn sequences from them.