Connected graphs without long paths (Q941391): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Paul N. Balister / rank
 
Normal rank
Property / author
 
Property / author: Ervin Gyoeri / rank
 
Normal rank
Property / author
 
Property / author: Jenő Lehel / rank
 
Normal rank
Property / author
 
Property / author: Richard H. Schelp / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Chunhui Lai / rank
 
Normal rank

Revision as of 18:09, 10 February 2024

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
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers