Connected graphs without long paths
From MaRDI portal
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}\).
Recommendations
Cites work
Cited in
(52)- Graphs without spanning closed trails
- Long path connectivity of regular graphs
- On extremal graphs with no long paths
- The spectral radius of graphs without long cycles
- Graphs without dead ends
- Connected hypergraphs without long Berge-paths
- Maxima of the \(Q\)-index: forbidden a Fan
- Inverse Turán numbers
- The Turán numbers of special forests
- Extremal graphs of the \(p\)th power of paths
- The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths
- Rainbow numbers for paths in planar graphs
- The Turań number of \(2P_7\)
- Planar Turán numbers of short paths
- The Turán number of disjoint copies of paths
- On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
- Turán numbers of multiple paths and equibipartite forests
- scientific article; zbMATH DE number 15461 (Why is no real title available?)
- Graphs with few paths of prescribed length between any two vertices
- Turán numbers for disjoint paths
- The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
- A note on maximum size of a graph without isolated vertices under the given matching number
- The maximum number of cliques in graphs with prescribed order, circumference and minimum degree
- Spectral radius of graphs forbidden C₇ or C₆^
- Stability of extremal connected hypergraphs avoiding Berge-paths
- Extremal graphs without long paths and a given graph
- How connectivity affects the extremal number of trees
- Extremal graphs without long paths and large cliques
- The Turán number of \(P_9 \cup P_7\)
- A Dirac-type theorem for uniform hypergraphs
- Stability of extremal connected hypergraphs avoiding Berge-paths
- Connected Turán number of trees
- The maximum number of \(P_\ell\) copies in \(P_k\)-free graphs
- On the Turán numbers of linear forests in bipartite graphs
- Linear three-uniform hypergraphs with no Berge path of given length
- Improved bounds on the multicolor Ramsey numbers of paths and even cycles
- Maximum spread of graphs without paths of specified length
- The rainbow numbers of paths in maximal bipartite planar graphs
- Generalized Turán problem for a path and a clique
- Extensions on spectral extrema of \(\theta_{1,2,5}\)-free graphs with given size
- The Turán number of three disjoint paths
- How connectivity affects the extremal number of trees (extended abstract)
- 3-uniform linear hypergraphs without a long Berge path (extended abstract)
- Spectral extremal problems for graphs with bounded clique number
- Spectral extrema of graphs: forbidden star-path forests
- On the maximum size of connected hypergraphs without a path of given length
- On the multi-colored Ramsey numbers of paths and even cycles
- A spectral Turán problem for a fixed tree
- A general theorem in spectral extremal graph theory
- Minimum degree of 3-graphs without long linear paths
- Maximum non-path-connected graphs
- The spectral radius of graphs without paths and cycles of specified length
This page was built for publication: Connected graphs without long paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q941391)
