On sequences of polynomials arising from graph invariants

DOI10.1016/J.EJC.2017.08.002MaRDI QIDQ2408975zbMATH OpenOpenAlexFDO

Authors Tomer Kotek, E. Ravve, Johann A. Makowsky

Publication date 10 October 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

matching polynomialsencoded graph invariant

Mathematics Subject Classification ID

Graph polynomials (05C31)

Abstract: Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebraic: The complete graphs $K_n$ and the complete bipartite graphs $K_{n,n}$ can be characterized as those graphs whose matching polynomials satisfy a certain recurrence relations and are related to the Hermite and Laguerre polynomials. An encoded graph invariant: The absolute value of the chromatic polynomial $chi(G,X)$ of a graph $G$ evaluated at $-1$ counts the number of acyclic orientations of $G$. In this paper we prove a general theorem on graph families which are characterized by families of polynomials satisfying linear recurrence relations. This gives infinitely many instances similar to the characterization of $K_{n,n}$. We also show where to use, instead of the Hermite and Laguerre polynomials, linear recurrence relations where the coefficients do not depend on $n$. Finally, we discuss the distinctive power of graph polynomials in specific form.

Recommendations

• Graph polynomials
• Recurrence relations for graph polynomials on bi-iterative families of graphs
• The graph polynomials and their equivalence
• Polynomial graph invariants from homomorphism numbers
• Graphs determined by polynomial invariants

Cites work

• scientific article; zbMATH DE number 4134043 (Why is no real title available?)
• scientific article; zbMATH DE number 3482387 (Why is no real title available?)
• scientific article; zbMATH DE number 3547324 (Why is no real title available?)
• scientific article; zbMATH DE number 3605240 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 1912564 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• scientific article; zbMATH DE number 272725 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• Chromatic invariants for finite graphs: Theme and polynomial variations
• Enumerative applications of a decomposition for graphs and digraphs
• Expansions of Chromatic Polynomials and Log-Concavity
• Graphs determined by polynomial invariants
• Hermite polynomials and a duality relation for matchings polynomials
• Linear Recurrence Relations for Graph Polynomials
• Matching theory
• On Counting Generalized Colorings
• On counting generalized colorings
• On graphs determined by their Tutte polynomials
• On the complexity of generalized chromatic polynomials
• On the location of roots of graph polynomials
• On the theory of the matching polynomial
• Polynomial graph invariants from homomorphism numbers
• Random matrices, magic squares and matching polynomials
• Recursive families of graphs
• Recursively constructible families of graphs
• Spectra of graphs
• Strongly polynomial sequences as interpretations
• The enumeration of vertex induced subgraphs with respect to the number of components
• The equivalence of two graph polynomials and a symmetric function
• The matching polynomial of a regular graph
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Unimodality, log-concavity, real-rootedness and beyond
• \( h\)-vectors of matroids and logarithmic concavity

Cited in

(12)

• On connection sequence for equivalent polynomial sets
• Recurrence relations for graph polynomials on bi-iterative families of graphs
• Genus polynomials of ladder-like sequences of graphs
• Discriminants, Symmetrized Graph Monomials, and Sums Of Squares
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Semantic equivalence of graph polynomials definable in second order logic
• A logician's view of graph polynomials
• Polynomials counting nowhere-zero chains in graphs
• scientific article; zbMATH DE number 3841912 (Why is no real title available?)
• Graph recurrence
• A sequence of complexes generated by a finite set of homogeneous polynomials
• On the complexity of generalized chromatic polynomials

This page was built for publication: On sequences of polynomials arising from graph invariants

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