Premium
Connectivity, graph minors, and subgraph multiplicity
Author(s) -
Eppstein David
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170314
Subject(s) - combinatorics , mathematics , multiplicity (mathematics) , induced subgraph isomorphism problem , graph , discrete mathematics , line graph , voltage graph , geometry
It is well known that any planar graph contains at most O ( n ) complete subgraphs. We extend this to an exact characterization: G occurs O ( n ) times as a subgraph of any planar graph, if and only if G is three‐connected. We generalize these results to similarly characterize certain other minor‐closed families of graphs; in particular, G occurs O ( n ) times as a subgraph of the K b,c ‐free graphs, b ≥ c and c ≤ 4, iff G is c ‐connected. Our results use a simple Ramsey‐theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.