Path-positive graphs

Abstract

For any positive integer k let P_k denote the characteristic polynomial of the adjacency matrix of the path on k vertices. We obtain certain results regarding P_k evaluated at A(G), the adjacency matrix of any given graph G. For some special graphs G, we describe the matrix P_k(A(G)) completely. We call a graph G path-positive if P_k(A(G)) is a nonnegative matrix for all positive integers k. It is shown that if G is a connected graph with a vertex of degree at least four, then G is path-positive. We conjecture that all connected graphs are path-positive apart from a few exceptional cases described in the paper.