A classification of graph capacity functions

Given two graphs G = (V(G), E(G)) and H = (V(H), E(H)), the sum of G and H, G + H, is the disjoint union of G and H. The product of G and H, G × H, is the graph with the vertex set V(G × H) that is the Cartesian product of V(G) and V(H), and two vertices (g₁, h₁), (g₂, h₂) are adjacent if and only if g₁, g₂] (ELEMENT) E(G) and h₁, h₂] (ELEMENT) E(H). Let G denote the set of all graphs. Given a graph G, the G-matching function, γ_G, assigns any graph H (ELEMENT) G to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, P_G: G → (RFRAKTUR), is defined as P_G(H) = lim_n→zγ_G(Hⁿ)]^1/n, where Hⁿ denotes the n-fold product of H × H × … × H. Different graphs G may have different graph capacity functions, all of which are increasing. In this paper, we classify all graphs whose capacity functions are additive, multiplicative, and increasing; all graphs whose capacity functions are pseudo-additive, pseudo-multiplicative, and increasing; and all graphs whose capacity functions fall under neither of the above cases. © 1996 John Wiley & Sons, Inc.