Connected graphs without long paths (Q941391)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connected graphs without long paths |
scientific article |
Statements
Connected graphs without long paths (English)
0 references
4 September 2008
0 references
The authors prove the following result: Let \(G\) be a connected graph on \(n\) vertices containing no path on \(k+1\) vertices, \(n>k\geq3\). Then \(|E(G)|\) is bounded above by the maximum of \({{k-1}\choose{2}}+(n-k+1)\) and \({{\lceil(k+1)/2\rceil}\choose{2}}+\lfloor(k-1)/2\rfloor(n-\lceil(k+1)/2\rceil)\). If equality occurs then \(G\) is either \(G_{n,k,1}\) or \(G_{n,k,\lfloor(k-1)/2\rfloor}\).
0 references
extremal graph
0 references
path
0 references
connected graph
0 references