A classification of graph capacity functions

✍ Scribed by Hsu, Lih-Hsing

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 893 KB
• Volume: 21
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199603)21:3<251::aid-jgt1>3.0.co;2-p

✦ Synopsis

Given two graphs G = (V(G), QG)) and H = (V(H), €(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 (gl, h l ) , (92, h2) are adjacent if and only if [ g l , 921 E €(G) and [ h l , h2] E €(I+). Let Cj denote the set of all graphs. Given a graph G, the G-matching function, Y G , assigns any graph H E Cj to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, PG : Cj -8, is defined as PG(H) = limW,[y~(Hn)]'/", where H" 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.