The Inducibility of Graphs
Document Type
Article
Department
Mathematics (HMC)
Publication Date
1975
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.
Rights Information
© 1975 Elsevier Ltd.
Terms of Use & License Information
DOI
10.1016/0095-8956(75)90084-2
Recommended Citation
Nicholas Pippenger, Martin Charles Golumbic, The inducibility of graphs, Journal of Combinatorial Theory, Series B, Volume 19, Issue 3, December 1975, Pages 189-203, ISSN 0095-8956, 10.1016/0095-8956(75)90084-2. (http://www.sciencedirect.com/science/article/pii/0095895675900842)
