Department of Mathematics, University of Illinois at Urbana-Champai, 1409, West Greeen Street, Urbana, IL 61801-2975, USA
Abstract:
Let ex* (D;H) be the maximum number of edges in a connected graph with maximum degree D and no induced subgraph H; this is finite if and only if H is a disjoint union of paths. If the largest component of such an H has order m, then ex*(D; H) = O(D2ex*(D; Pm)). Constructively, ex*(D;qPm) = Θ(gD2ex*(D;Pm)) if q>1 and m> 2(Θ(gD2) if m = 2). For H = 2P3 (and D 8), the maximum number of edges is
if D is even and