Properties of the Extended Graph Permanent

Abstract

Previously, the graph permanent was introduced as a single-valued invariant for graphs $G$ with $|E(G)|=k(|V(G)|-1)$ for some $k\in {\mathbb{Z}}_{>0}$. Herein, we construct the extended graph permanent, an infinite sequence for all graphs. We prove that, like the graph permanent, the extended graph permanent is invariant under the graph operations that are known to preserve the period. Further, the original construction and extension arise from permanents of matrices, but we construct a novel graph polynomial such that the sequence can be generated from the point count of this polynomial, as a residue over prime-order finite fields.

40 pages, 4 figures, containing corrections from referee reports