On sequences of polynomials arising from graph invariants

DOI10.1016/J.EJC.2017.08.002zbMATH Open1371.05135arXiv1701.08564OpenAlexW2584135402MaRDI QIDQ2408975FDOQ2408975

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

Publication date: 10 October 2017

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

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.

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

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

zbMATH Keywords

matching polynomialsencoded graph invariant

Mathematics Subject Classification ID

Graph polynomials (05C31)

Cites Work

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

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
• Title not available (Why is that?)
• A sequence of complexes generated by a finite set of homogeneous polynomials
• Graph recurrence
• 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)