標題: A classification of graph capacity functions
作者: Hsu, LH
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
公開日期: 1-三月-1996
摘要: 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.
URI: http://hdl.handle.net/11536/1436
ISSN: 0364-9024
期刊: JOURNAL OF GRAPH THEORY
Volume: 21
Issue: 3
起始頁: 251
結束頁: 265
顯示於類別:期刊論文


文件中的檔案:

  1. A1996TW40900001.pdf