Polynomial reconstruction of the matching polynomial

DOI10.5614/EJGTA.2015.3.1.4MaRDI QIDQ5006550zbMATH OpenOpenAlexFDO

Authors Yongtang Shi, Martin Trinks, Xueliang Li

Publication date 16 August 2021

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1404.3469

zbMATH Keywords

matching polynomialperfect matchingreconstruction

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex-deleted subgraphs of the same graph. This note discusses the polynomial reconstructibility of the matching polynomial. We collect previous results, prove it for graphs with pendant edges and disprove it for some graphs.

Recommendations

• On the reconstruction of the matching polynomial and the reconstruction conjecture
• Polynomial reconstruction and terminal vertices
• Reconstructing subgraph-counting graph polynomials of increasing families of graphs
• scientific article; zbMATH DE number 2061158
• On maximal matchings of connected graphs

Cites work

• A congruence theorem for trees
• A unified approach to the first derivatives of graph polynomials
• An introduction to matching polynomials
• Hermite polynomials and a duality relation for matchings polynomials
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3739586 (Why is no real title available?)
• scientific article; zbMATH DE number 166023 (Why is no real title available?)
• scientific article; zbMATH DE number 3583866 (Why is no real title available?)
• Matching theory
• Matchings and walks in graphs
• On the reconstruction of the matching polynomial and the reconstruction conjecture
• Reconstructing subgraph-counting graph polynomials of increasing families of graphs
• The enumeration of vertex induced subgraphs with respect to the number of components

Cited in

(11)

• The matching polynomial of a polygraph
• On the reconstruction of the matching polynomial and the reconstruction conjecture
• The idiosyncratic polynomial of digraphs
• A note on \(m\)-near-factor-critical graphs
• Reconstructing subgraph-counting graph polynomials of increasing families of graphs
• Higher order matching polynomial
• Proving properties of the edge elimination polynomial using equivalent graph polynomials
• Uniqueness of the matching polynomial
• scientific article; zbMATH DE number 3954967 (Why is no real title available?)
• Reconstruction of a Polynomial from Its Radon Projections
• The matching polynomials of hypergraphs and weighted hypergraphs

This page was built for publication: Polynomial reconstruction of the matching polynomial

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