Graph characterising polynomials

DOI10.1016/S0012-365X(98)00403-8MaRDI QIDQ1304820zbMATH OpenOpenAlexFDO

Authors K. R. Parthasarathy

Publication date 9 April 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(98)00403-8

zbMATH Keywords

frame polynomialgraph characterizing polynomialsgraph reconstruction conjecturepermanent polynomial

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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.

Recommendations

• Algebraic invariants of graphs; a study based on computer exploration
• On the bivariate permanent polynomials of graphs
• The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements
• Generalized permanental polynomials of graphs
• scientific article; zbMATH DE number 4154487
• scientific article; zbMATH DE number 1191252
• Seeking counterexamples to the reconstruction conjecture for the characteristic polynomial of graphs and a positive results
• On the polynomial reconstruction of graphs whose vertex-deleted subgraphs have spectra bounded from below by \(-2\)
• The polynomial reconstruction of unicyclic graphs is unique
• Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems

Cited in

(15)

• Farrell polynomials on graphs of bounded tree width
• Finite-type invariants for graphs and graph reconstructions
• The idiosyncratic polynomial of digraphs
• Highly unique network descriptors based on the roots of the permanental polynomial
• Generalized permanental polynomials of graphs
• On the bivariate permanent polynomials of graphs
• Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems
• On the reconstruction of graph invariants
• scientific article; zbMATH DE number 6378508 (Why is no real title available?)
• Polynomial Invariants of Graphs
• Note on the subgraph component polynomial
• scientific article; zbMATH DE number 1225797 (Why is no real title available?)
• scientific article; zbMATH DE number 2144997 (Why is no real title available?)
• Algebraic invariants of graphs; a study based on computer exploration
• Blowup polynomials and delta-matroids of graphs

This page was built for publication: Graph characterising polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1304820)