Large \(2P_ 3\)-free graphs with bounded degree (Q1916098)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Large \(2P_ 3\)-free graphs with bounded degree |
scientific article |
Statements
Large \(2P_ 3\)-free graphs with bounded degree (English)
0 references
21 November 1996
0 references
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.
0 references
forbidden subgraph
0 references
maximum degree
0 references
disjoint paths
0 references
extremal graph
0 references