Contractors and connectors of graph algebras

DOI10.1002/JGT.20343zbMATH Open1189.05115arXivmath/0505162OpenAlexW2949221968MaRDI QIDQ3605157FDOQ3605157

Authors: Balázs Szegedy, László Lovász 

Publication date: 20 February 2009

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We study generalizations of the "contraction-deletion" relation of the Tutte polynomial, and other similar simple operations, to other graph parameters. The question can be set in the framework of graph algebras introduced by Freedman, Lovasz and Schrijver, and it relates to their behavior under basic graph operations like contraction and subdivision. Graph algebras were introduced to study and characterize homomorphism functions. We prove that for homomorphism functions, these graph algebras have special elements called ``contractors and ``connectors. This gives a new characterization of homomorphism functions.

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

Recommendations

• Homomorphisms and polynomial invariants of graphs
• Contraction-deletion invariants for graphs
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Homomorphisms and Polynomial Invariants of Graphs
• Weighted graph homomorphisms and the Tutte polynomial

zbMATH Keywords

graph homomorphismTutte polynomialconnectorgraph algebracontractorcontraction-deletionhomomorphism functions

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Limits of dense graph sequences
• Moments of two-variable functions and the uniqueness of graph limits
• The rank of connection matrices and the dimension of graph algebras
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Generalized quasirandom graphs

Cited In (15)

• On recognizing graphs by numbers of homomorphisms
• Local WL invariance and hidden shades of regularity
• The contractum in algebraic graph rewriting
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Connector algebras for C/E and P/T nets' interactions
• Graphon convergence of random cographs
• Estimating and understanding exponential random graph models
• Semidefinite functions on categories
• Graph parameters from symplectic group invariants
• Edge cut splitting formulas for Tutte-Grothendieck invariants
• The large deviation principle for the Erdős-Rényi random graph
• On the number of \(B\)-flows of a graph
• Contractors for flows
• Contractors for flows
• Finitely forcible graphons

This page was built for publication: Contractors and connectors of graph algebras

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