Bipartite graphs containing every possible pair of cycles (Q1817575)

From MaRDI portal
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