On independent cycles and edges in graphs (Q1910587)

From MaRDI portal
Revision as of 07:56, 20 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: author (P16): Item:Q689954)
scientific article
Language Label Description Also known as
English
On independent cycles and edges in graphs
scientific article

    Statements

    On independent cycles and edges in graphs (English)
    0 references
    26 March 1996
    0 references
    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\).
    0 references
    extremal graphs
    0 references
    independent cycles
    0 references

    Identifiers