COMMENTS ON THE CHARACTERISTIC POLYNOMIAL OF A GRAPH

Several unique advantages of the Le Verrier-Fadeev-Frame method for the characteristic polynomials of graphs over the method proposed by Zivkovic recently based on the Givens-Householder method are described. It is shown that the Givens-Householder method proposed by Zivkovic, by itself fails for directed graphs, signed graphs, and complex nonhermetian graphs requiring extensive modifications to the Householder algorithm through the double + random shift QR procedure requiring more computations than claimed. Furthermore, the QR procedure does not always converge and requires random shifts. To the contrary, it is shown that the Le Verrier-Fadeev-Frame method does not require any such modifications or random shifts and takes less total CPU times when both algorithms are run using vector processors. Hence it is demonstrated that the Le Verrier-Frame algorithm is efficient and superior in its universal and direct applicability to all graphs requiring no further modifications (directed, signed, and complex).