Connected graphs without long paths (Q941391)

From MaRDI portal
Revision as of 18:09, 10 February 2024 by RedirectionBot (talk | contribs) (‎Removed claims)
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

    Identifiers