Graph characterising polynomials
type: Item
instance of: scholarly article
title: Graph characterising polynomials
zbMATH Open document ID: 0934.05093
DOI: 10.1016/S0012-365X(98)00403-8
author: K. R. Parthasarathy
published in: Discrete Mathematics
publication date: 2000-04-09T00:00:00Z
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.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1340374
zbMATH Keywords: graph characterizing polynomials
zbMATH Keywords: graph reconstruction conjecture
zbMATH Keywords: permanent polynomial
zbMATH Keywords: frame polynomial
reviewed by: Robert R. Molina
MaRDI profile type: Publication
full work available at URL: s0012-365x(98)00403-8
OpenAlex ID: W1980628171
Recommended article: Algebraic invariants of graphs; a study based on computer exploration
Recommended article: On the bivariate permanent polynomials of graphs
Recommended article: The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements
Recommended article: Generalized permanental polynomials of graphs
Recommended article: Q3483310
Recommended article: Q3842569
Recommended article: Seeking counterexamples to the reconstruction conjecture for the characteristic polynomial of graphs and a positive results
Recommended article: On the polynomial reconstruction of graphs whose vertex-deleted subgraphs have spectra bounded from below by \(-2\)
Recommended article: The polynomial reconstruction of unicyclic graphs is unique
Recommended article: Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems
description: scientific article; zbMATH DE number 1340374