A classification of graph capacity functions

Abstract

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 x H, is the graph with the vertex set V(G x H) that is the Cartesian product of V(G) and V(H), and two vertices (g(1), h(1)), (g(2), h(2)) are adjacent if and only if [g(1), g(2)] epsilon E(G) and [h(1), h(2)] epsilon E(H). Let G denote the set of all graphs. Given a graph G, the G-matching function, gamma(G), assigns any graph H epsilon G to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, P-G : G --> R, is defined as P-G(H) = lim(n-->infinity)[gamma(G)(H-n)](1/n), where H-n denotes the n-fold product of H x H x ... x 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. (C) 1996 John Wiley & Sons, Inc.