The inducibility of graphs
The inducibility of graphs
复制标题
图的可归纳性
DOI：
10.1016/0095-8956(75)90084-2
复制
发表时间：
1975
期刊：
影响因子：
--
通讯作者：
M. Golumbic
中科院分区：
文献类型：
--
作者：
N. Pippenger;M. Golumbic
本文研究了Ak-点图G作为n-点图的导出子图出现的最大数目，当这个数目被表示为所有k-点导出子图的分数时，它趋向于一个确定的极限为N，≥，→∞。这个极限，我们称之为G的可归纳性，是G的一个有效的可计算不变量。我们研究了这个不变量的基本性质：它与图上的各种运算的关系，它的最大值和最小值，以及它对某些特定图的值。
We investigate the maximum number of ways in which ak-vertex graphGcan appear as an induced subgraph of ann-vertex graph, forn≥k. When this number is expressed as a fraction of allk-vertex induced subgraphs, it tends to a definite limit asn→ ∞. This limit, which we call theinducibilityofG, is an effectively computable invariant ofG. We examine the elementary properties of this invariant: its relationship to various operations on graphs, its maximum and minimum values, and its value for some particular graphs.