
doi: 10.1007/bf02579234
(From the authors' abstract:) ``Let \(L\) be a given family of \dots 'prohibited graphs'. Let \(\text{ex}(n,L)\) denote the maximum number of edges a simple graph of order n can have without containing subgraphs from \(L\). A typical extremal graph problem is to determine \(\text{ex}(n,L)\), or, at least, to find good bounds on it. Results asserting that, for a given \(L\), there exists a 'much smaller' \(L^*\subset L\) for which \(\text{ex}(n,L)\approx \text{ex}(n,L^*)\) will be called compactness results. The main purpose of this paper is to prove some compactness results for the case when \(L\) consists of cycles. One of our main tools will be finding lower bounds on the number of paths \(p^{k+1}\) in a graph on \(n\) vertices and \(E\) edges \dots a `supersaturated' version of a well known theorem of Erdős and Gallai.'' Among the theorems proved, presented in the context of open conjectures, are: Theorem 1: Let \(k\) be a natural number. Then \(\text{ex}(n,\{C^3,\dots,C^{2k},C^{2k+1}\})\leq(n/2)^{1+(1/k)}+2^k\cdot(n/2)^{1-(1/k)}\). Theorem 2: \(\text{ex}(n,\{C^4,C^5\})=(n/2)^{3/2}+0(n)\). Theorem 3*: Let \(T\) be a tree with a fixed 2-colouring: A graph \(L\) is obtained from \(T\) by joining a new vertex to each vertex of one colour class by disjoint paths, each k edges long. Then, if \(\text{ex}(n,L)\geq cn^{1+(1/k)}\), then is a \(t\) for which \[ \lim_{n\to\infty}(ex(n,\{L,C^3,C^5,\dots\})/ex(n,\{L,C^3,C^5,\dots,C^{2_{t-1}}\}))=1 \] Theorem 5: If \(f(n,d)\) is the minimum number of walks \(W^{k+1}\) a graph \(G^n\) can have with average degree \(d\), then every graph of order \(n\) and average degree \(d\) contains at least \((1/2)\cdot f(n,d)-0(f(n,d))\) paths \(p^{k+1}\), as \(d\to\infty\).
Extremal problems in graph theory, disjoint paths, Coloring of graphs and hypergraphs, extremal graph, compactness, supersaturated, Paths and cycles
Extremal problems in graph theory, disjoint paths, Coloring of graphs and hypergraphs, extremal graph, compactness, supersaturated, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 72 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
