On independent cycles and edges in graphs (Q1910587): Difference between revisions

Denote by \(\langle n\rangle\) the complete graph \(K_n\), by \(\langle p, q\rangle\) the complete bipartite graph \(K_{pq}\), and by \(\langle\langle p\rangle, q\rangle\) the graph obtained from \(\langle p, q\rangle\) by converting the \(p\)-vertex set to \(K_p\). For positive integers \(n\) and \(k\), let \(f(n, k)\) be the number of edges of the graph \(\langle\langle 2k- 1\rangle, n- 2k+ 1\rangle\) and \(g(n, k)\) the number of edges of the graph obtained from \(\langle 3k- 1\rangle\) by attaching \(n- 3k+ 1\) pendant edges. \textit{P. Justesen} [Ann. Discrete Math. 41, 299-305 (1989; Zbl 0673.05065)] proved that, for any integer \(k\geq 2\), if \(G\) is a graph on \(n\) vertices such that \(n\geq k\) and \[ e(G)\geq \max\{f(n, k), g(n, k)+ 1\}, \] then \(G\) contains \(k\) vertex-disjoint (``independent'') cycles or \(G\simeq \langle\langle 2k- 1\rangle, n- 2k+ 1\rangle\). Using Justesen's argument, the author extends his result by determining the corresponding extremal graphs, i.e., the graphs \(G\) with \(e(G)= \max\{f(n, k), g(n, k)\}\), which do not contain \(k\) independent cycles. A modification of the same proof leads to the solution of the following problem: For integers \(k\), \(s\) with \(0\leq s\leq k\) and \(k\geq 2\), let \({\mathcal G}(n, k, s)\) be the class of graphs on \(n\) vertices not containing \(k\) independent subgraphs of which \(k- 2\) are cycles and the rest \(K_2\)'s. Determine those graphs in \({\mathcal G}(n, k, s)\) with the maximum number of edges for \(n\geq 3k- s\).