Ronald Fagin, Jurg Nievergelt, et al.
ACM Transactions on Database Systems (TODS)
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. © 1975.
Ronald Fagin, Jurg Nievergelt, et al.
ACM Transactions on Database Systems (TODS)
Maria Klawe, Wolfgang J. Paul, et al.
STOC 1984
Nicholas Pippenger
STOC 1976
Martin Charles Golumbic, Vladimir Rainish
Scientific Programming