A partially ordered set of functionals corresponding to graphs

✍ Scribed by Alexander Sidorenko

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 776 KB
• Volume: 131
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90388-3

✦ Synopsis

For a graph G whose vertices are vl, u2, . . . , v, and where E is the set of edges, we define a functional U,(h)= ss SC . . . frl,$EEh(Xi,Xj) > dPc(x~)dAxJ ... dp(x,), where h is a nonnegative symmetric function of two variables. We consider a binary relation + for graphs with fixed numbers of vertices and edges, where G+L means that U,(h) 2 U,(h) for every h. We prove that this relation is equivalent to the condition: the number of homomorphisms into every graph H from G is not less than from L. We obtain comparability and incomparability criteria and investigate the poset of k-edge trees. In particular, the first and the second maximal elements of this poset are found.