The underlying line digraph structure of some (0, 1)-matrix equations (Q5957359): Difference between revisions

It is known that the adjacency matrix \({\mathbf A}\) of a strongly connected regular digraph of order \(n\) satisfies a certain polynomial equation \({\mathbf A}^l P({\mathbf A})={\mathbf J}_n\), where \(l\) is a nonnegative integer, \(P(x)\) is a polynomial with rational coefficients, and \({\mathbf J}_n\) is the \(n\times n\) matrix of all ones. The paper presents some sufficient conditions in terms of the coefficients of \(P(x)\) to ensure that all \((0,1)\)-matrices satisfying such an equation with \(l>0\) have an underlying line digraph structure. In other words, for any solution \({\mathbf A}\) there exists a \((0,1)\)-matrix \({\mathbf C}\) satisfying \(P({\mathbf C})={\mathbf J}_{n/d^l}\) and the associated \(d\)-regular digraph of \({\mathbf A}\), \(\Gamma({\mathbf A})\), is the \(l\)th iterated line digraph of \(\Gamma({\mathbf C})\). As a result, the study of some digraph classes with order functions can asymptotically attain the Moore bound.