Large 2P3-free graphs with bounded degree

✍ Scribed by Myung S. Chung; Douglas B. West

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 541 KB
• Volume: 150
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00176-w

✦ Synopsis

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) = O(qD2ex*(D;Pm)) if q>l and m>2 (O(qD 2) if m = 2). For H = 2P3 (and D ~> 8), the maximum number of edges is ½ [D 4 + D 3 + D 2 + 6D] if D is even and ½ [D 4 + 0 3 + 2D 2 + 3D + 1 ] if D is odd, achieved by a unique extremal graph.