Generalized homomorphism graph functions (Q753838): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:08, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalized homomorphism graph functions |
scientific article |
Statements
Generalized homomorphism graph functions (English)
0 references
1990
0 references
Lovász posed the problem of characterizing all real-valued functions f on finite graphs which are increasing \((f(G)\leq f(H)\) if G is a subgraph of H) and multiplicative \((f(G\times H)=f(G)\cdot f(H),\) for the conjunction, or categorical product \(\times)\). The author has earlier given several classes of such functions, and he presents here a new class, properly extending a class defined previously. The new class consists of functions \(\phi_{G,S}\), whose value \(\phi_{G,S}(H)\) is defined to be the number of distinct restrictions \(f| S\) of homomorphisms f: \(G\mapsto H\) to the fixed set \(S\subseteq V(G)\). Lovász observed that the class of increasing multiplicative functions was closed under taking products, positive powers, and pointwise limits, and asked whether a certain class of functions generated all increasing multiplicative functions by the above operations. The author has shown previously that this was not so. The new class of functions \(\phi_{G,S}\) extends the basic class proposed by Lovász, but is still not large enough to generate all increasing multiplicative functions by products, positive powers, and pointwise limits. Similar questions are also considered for the Cartesian product, and for functions f which are increasing, multiplicative, and additive \((f(G+H)=f(G)+f(H),\) for the disjoint union \(+)\).
0 references
graph products
0 references
increasing multiplicative functions
0 references