Graph characterising polynomials (Q1304820): Difference between revisions

A graph invariant is a function \(f\) from the class of all graphs into a commutative ring \(R\) such that \(f\) takes the same value on isomorphic graphs. If \(R\) is a ring of polynomials in one or more variables, the invariant \(f\) is called an invariant polynomial for graphs. If \(f\) satisfies the converse condition that \(f(G)=f(H)\) implies \(G\cong H\), then \(f\) is called a characterizing polynomial. The two invariant polynomials that are considered in this paper are the bivariate permanent polynomial and the frame polynomial. The conjectures that these are graph characterizing polynomials are denoted PC and FC respectively. These conjectures have been verified for graphs on up to 7 vertices, and it is known that PC implies FC. The author shows that these conjectures imply the famous graph reconstruction conjecture, and suggests a possible approach to settle PC using \textit{V. B. Mnukhin}'s [Acta Appl. Math. 29, No. 1-2, 83-117 (1992; Zbl 0769.05069)] characterization of a complete set of graph invariants. The problem of determining the number of single vertex components of a graph from its permanent polynomial is also considered.