Det är väl känt att någon planar graf innehåller högst O(n) fullständiga subgrafer. Vi utökar detta till en exakt karakterisering: G förekommer O(n) gånger som en del av någon planar graf, om och endast om G är tre ansluten. Ännu mer allmänt, G förekommer O(n) gånger som en subgraf av K b,c - fria grafer, b ≥ c, om och endast om G är c- ansluten; G förekommer O (n) gånger som en subgraf av K a - fria grafer om och endast om G är (a - 1)- ansluten. Våra resultat använder en enkel Ramsey-teoretisk lemma som kan vara av oberoende intresse.
Nyligen kunde vi karakterisera de grafer som kan förekomma som mest O(n) gånger som en subgraph isomorf i en n-vertex planar graf: de är exakt de 3-anslutna planar grafer REF.
Connectivity, Graph Minors, and Subgraph Multiplicity
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}