On the bipartite case of El-Zahár's conjecture (Q1567667)

From MaRDI portal





scientific article; zbMATH DE number 1462322
Language Label Description Also known as
English
On the bipartite case of El-Zahár's conjecture
scientific article; zbMATH DE number 1462322

    Statements

    On the bipartite case of El-Zahár's conjecture (English)
    0 references
    0 references
    5 November 2000
    0 references
    A conjecture of El-Zahár says that if a graph \(G\) has \(n = n_1 + \cdots + n_k\) vertices and minimum degree at least \(\lceil n_1/2 \rceil + \cdots + \lceil n_k/2 \rceil\), then \(G\) has a spanning subgraph made up of disjoint cycles of lengths \(n_1, \ldots , n_k\). Taking the case when each \(n_i\) is 4, the author proves that if \(|G|= 4k\) and \(\delta \geq 2k\) then \(G\) has a spanning subgraph made up of \(k-1\) independent 4-cycles and one 4-path. He goes on to show that such \(G\) is spanned by \((k-2)\) 4-cycles and one 8-cycle.
    0 references
    spanning subgraph
    0 references

    Identifiers