The inducibility of graphs |
| |
Authors: | Nicholas Pippenger Martin Charles Golumbic |
| |
Institution: | Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598 USA;Department of Mathematics, Columbia University, New York, New York 10027 USA |
| |
Abstract: | We investigate the maximum number of ways in which a k-vertex graph G can appear as an induced subgraph of an n-vertex graph, for n ≥ k. When this number is expressed as a fraction of all k-vertex induced subgraphs, it tends to a definite limit as n → ∞. This limit, which we call the inducibility of G, is an effectively computable invariant of G. 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|