Large \(2P_ 3\)-free graphs with bounded degree
type: Item
instance of: scholarly article
title: Large \(2P_ 3\)-free graphs with bounded degree
zbMATH Open document ID: 0851.05067
DOI: 10.1016/0012-365X(95)00176-W
author: Myung S. Chung
author: Douglas B. West
published in: Discrete Mathematics
publication date: 1996-11-21T00:00:00Z
review text: By \(\text{ex}^*(D, H)\) the maximum number of edges of a connected graph with maximum degree \(D\) and no induced subgraph \(H\) is denoted. This number is finite if and only if \(H\) is a disjoint union of paths. First some remarks on the general case are done. Then a particular case is studied, namely the union \(2P_3\) of two disjoint paths \(P_3\). For \(D\geq 8\) the number \(\text{ex}^*(D, 2P_3)\) is proved to be equal to \({1\over 8} (D^4+ D^3+ D^2+ 6D)\) for \(D\) even and to \({1\over 8} (D^4+ D^3+ 2D^2- 3D+ 1)\) for \(D\) odd. The corresponding extremal graph is unique.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 895988
zbMATH Keywords: forbidden subgraph
zbMATH Keywords: maximum degree
zbMATH Keywords: disjoint paths
zbMATH Keywords: extremal graph
MaRDI profile type: Publication
cites work: Q3852212
cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
cites work: Large P4‐free graphs with bounded degree
description: scientific article; zbMATH DE number 895988