Artículo
Polynomial graph invariants from homomorphism numbers
Autor/es | Garijo Royo, Delia
Goodall, Andrew Nesetril, Jaroslav |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2016 |
Fecha de depósito | 2020-06-20 |
Publicado en |
|
Resumen | We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences
(Hk) indexed by a tuple k = (k1, . . . , kh) of positive integers, with the property
that, for each fixed graph G, there is a ... We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences (Hk) indexed by a tuple k = (k1, . . . , kh) of positive integers, with the property that, for each fixed graph G, there is a multivariate polynomial p(G; x1, . . . , xh) such that the number of homomorphisms from G to Hk is given by the evaluation p(G; k1, . . . , kh). A classical example is the sequence of complete graphs (Kk), for which p(G; x) is the chromatic polynomial of G. Our construction is based on tree model representations of graphs. It produces a large family of graph polynomials which includes the Tutte polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial. We also introduce a new graph parameter, the branching core size of a simple graph, derived from its representation under a particular tree model, and related to how many involutive automorphisms it has. We prove that a countable family of graphs of bounded branching core size is always contained in the union of a finite number of strongly polynomial sequences. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | MTM2014-60127-P |
Cita | Garijo Royo, D., Goodall, A. y Nesetril, J. (2016). Polynomial graph invariants from homomorphism numbers. Discrete mathemtaics, 339 (4), 1315-1328. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Polynomial graph invariants.pdf | 498.7Kb | [PDF] | Ver/ | |