The Inducibility of Graphs

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow
Martin Charles Golumbic, Columbia University

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

Terms of Use for work posted in Scholarship@Claremont.

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)