Bipartite graphs containing every possible pair of cycles (Q1817575)

From MaRDI portal
Revision as of 10:34, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Bipartite graphs containing every possible pair of cycles
scientific article

    Statements

    Bipartite graphs containing every possible pair of cycles (English)
    0 references
    0 references
    8 May 2000
    0 references
    A result of \textit{D. Amar} [Discrete Math. 53, 1-10 (1986; Zbl 0587.05044)] states that a bipartite graph \(G = V_1 \cup V_2\) where \(|V_1|= |V_2|= n \geq 4\) for which \(d(x) + d(y) \geq n+2\) for all \(x \in V_1\) and \(y \in V_2\) contains two vertex-disjoint cycles of lengths \(2s\) and \(2t\), respectively, whenever \(s+t = n\) (\(s, t \geq 2\)). Wang extends the result to any pair \(s,t\) satisfying \(s+t \leq n\) by using a theorem of \textit{J. A. Bondy} and \textit{V. Chvátal} [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)].
    0 references
    0 references
    bipartite graph
    0 references
    vertex-disjoint cycles
    0 references