×

Generalized degrees and short even cycles. (English) Zbl 0836.05049

Summary: Let \(G\) be a graph of order \(n\) such that \(|E(G) |> c_k n^{{k + 1 \over k}}\). In 1963 P. Erdös showed that this implies \(G\) contains a \(C_{2k}\). He conjectured that this edge density condition implies \(G\) contains a \(C_{2l}\) for every integer \(l \in [k, n^{{1 \over k}}]\). In 1974 J. A. Bondy and M. Simonivits [J. Comb. Theory, Ser. B 16, 97-105 (1974; Zbl 0283.05108)] proved the conjecture with \(c_k = 100k\). The purpose of this paper is to provide a generalized degree analogue to this classic result of Erdös. Here we use the following idea of generalized minimum degree. Let \(\delta_k (G) = \min |N(u_1) \cup N (u_2) \cup \cdots \cup N (u_k) |\) where the minimum is taken over all independent sets of vertices \(\{u_1, \dots, u_k\}\) of size \(k\) and \(N(u_i)\) denotes the neighborhood of the vertex \(u_i\). We call \(\delta_k (G)\) the minimum generalized \(k\)-degree for \(G\).

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles

Citations:

Zbl 0283.05108
PDFBibTeX XMLCite