On extremal graphs with no long paths

MaRDI QIDQ1379162zbMATH OpenFDO

Authors Ali A. Ali, William Staton

Publication date 22 February 1998

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119217, http://www.emis.de/journals/EJC/Volume_3/volume3.html#R20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

characterizationextremal graphspaths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

Summary: Connected graphs with minimum degree \(\delta\) and at least \(2\delta+ 1\) vertices have paths with at least \(2\delta+ 1\) vertices. We provide a characterization of all such graphs which have no longer paths.

Recommendations

• Connected graphs without long paths
• scientific article; zbMATH DE number 568796
• Minimum degree of 3-graphs without long linear paths
• Long paths and large cycles in finite graphs

Cited in

(10)

• Extremal 3-connected graphs
• Erdős-Gallai stability theorem for linear forests
• Maxima of the \(Q\)-index: forbidden odd cycles
• scientific article; zbMATH DE number 568796 (Why is no real title available?)
• Extremal digraphs whose walks with the same initial and terminal vertices have distinct lengths
• Some results on graphs without long induced paths
• On Subtrees of Directed Graphs with No Path of Length Exceeding One
• Ramsey numbers of large even cycles and fans
• Stability in Bondy's theorem on paths and cycles
• Connected graphs without long paths

This page was built for publication: On extremal graphs with no long paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1379162)