**Connectivity, graph minors, and subgraph multiplicity**.

D. Eppstein.

Tech. Rep. 92-06, ICS, UCI, 1992.

*J. Graph Th.*17: 409–416, 1993.It was known that planar graphs have O(

*n*) subgraphs isomorphic to K_{3}or K_{4}. That is, K_{3}and K_{4}have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.More generally, let F be a minor-closed family, and let x be the smallest number such that some complete bipartite graph K

_{x,y}is a forbidden minor for F. Then the x-connected graphs have linear subgraph multiplicity for F, and there exists an (x − 1)-connected graph (namely K_{x − 1,x − 1}) that does not have linear subgraph multiplicity. When x ≤ 3 or when x = 4 and the minimal forbidden minors for F are triangle-free, then the graphs with linear subgraph multiplicity for F are exactly the x-connected graphs.Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.

Journals – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.