Connectivity, graph minors, and subgraph multiplicity | Zendy

Eppstein David | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research